Skip to content

235. Lowest Common Ancestor of a Binary Search Tree 👍

  • Time: $O(h)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root->val > max(p->val, q->val))
      return lowestCommonAncestor(root->left, p, q);
    if (root->val < min(p->val, q->val))
      return lowestCommonAncestor(root->right, p, q);
    return root;
  }
};

1
2
3
4
5
6
7
8
9
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > Math.max(p.val, q.val))
      return lowestCommonAncestor(root.left, p, q);
    if (root.val < Math.min(p.val, q.val))
      return lowestCommonAncestor(root.right, p, q);
    return root;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def lowestCommonAncestor(
      self,
      root: 'TreeNode',
      p: 'TreeNode',
      q: 'TreeNode',
  ) -> 'TreeNode':
    if root.val > max(p.val, q.val):
      return self.lowestCommonAncestor(root.left, p, q)
    if root.val < min(p.val, q.val):
      return self.lowestCommonAncestor(root.right, p, q)
    return root