Problem statement

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Solution

In this problem we have BST so we can use this property. We use dfs(root) function, and we can have options:

  1. root.val > max(p.val, q.val): in this case we do not have any option except of going to the left: all right subtree is too big for us because of BST property.
  2. root.val < min(p.val, q.val): in this case we go to the right, because all left subtree is too small.
  3. Finally if we have root.val between min(p.val, q.val) and max(p.val, q.val), it means that we found desired node

Complexity

Time and space complexity is O(h): the height of our tree. It can go upto n, but for balanced BST it is O(log n).

Code

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        self.Found = None
        
        def dfs(root):
            if root.val > max(p.val, q.val):
                dfs(root.left)
            elif root.val < min(p.val, q.val):
                dfs(root.right)
            else:
                self.Found = root
                
        dfs(root)
        return self.Found