< Back





235. Lowest Common Ancestor of a Binary Search Tree

Given two nodes, p and q, we're asked to find the lowest common ancestor of each node in a binary
search tree. The nodes themselves can also be the lowest common ancestor. Given that this is a
binary search tree, we can use the values of p and q to direct our search either left or right.
But, if the values of p and q are not greater than the current node or less than the current node,
we know that we've found the lowest common ancestor.

The solution is as follows:


  class Solution:
      def lowestCommonAncestor(self, root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
          if not root:
              return

          if p.val < root.val and q.val < root.val:
              return self.lowestCommonAncestor(root.left, p, q)
          if p.val > root.val and q.val > root.val:
              return self.lowestCommonAncestor(root.right, p, q)
          else:
              return root


_ Time Complexity:

  O(n) - Where n is the number of nodes in the binary search tree.

_ Space Complexity:

  O(n) - Our recursive function can be called n times.