MediumBlind75TreeDFSBST

Lowest Common Ancestor of a Binary Search Tree

Given a BST, find the lowest common ancestor (LCA) of two given nodes in the BST.

Examples

Input
root = [6,2,8,0,4,7,9,null,null,null,3,5], p = 2, q = 8
Output
6

The LCA of 2 and 8 is 6.

Input
root = [6,2,8,0,4,7,9,null,null,null,3,5], p = 2, q = 4
Output
2

The LCA of 2 and 4 is 2.

Constraints

  • •The number of nodes in the tree is in the range [2, 10^5]
  • •-10^9 <= Node.val <= 10^9
  • •All Node.val are unique.
  • •p != q
  • •p and q will exist in the BST.

Approaches

Find all ancestors of p and q, then find the deepest common ancestor.

CodeT: O(n) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor(root, p, q):
    def get_ancestors(node, target, ancestors):
        if not node:
            return False
        if node.val == target.val:
            ancestors.append(node)
            return True
        if get_ancestors(node.left, target, ancestors) or get_ancestors(node.right, target, ancestors):
            ancestors.append(node)
            return True
        return False
    p_ancestors = []
    q_ancestors = []
    get_ancestors(root, p, p_ancestors)
    get_ancestors(root, q, q_ancestors)
    p_set = set(id(a) for a in p_ancestors)
    for a in q_ancestors:
        if id(a) in p_set:
            return a
    return None

Use BST property: go left if both smaller, go right if both larger, else root is LCA.

CodeT: O(h) | S: O(1)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor(root, p, q):
    curr = root
    while curr:
        if p.val < curr.val and q.val < curr.val:
            curr = curr.left
        elif p.val > curr.val and q.val > curr.val:
            curr = curr.right
        else:
            return curr

Same BST property implemented recursively.

Diagram

BST: 6->2,8->0,4->3,5 LCA(2,8): 2<6 and 8>6 -> split -> return 6 LCA(2,4): 2<6 and 4<6 -> go left 2==2 -> split -> return 2
CodeT: O(h) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor(root.right, p, q)
    return root

Complexity Comparison

Check All Ancestors
T: O(n)S: O(h)

Find all ancestors of p and q, then find the deepest common ancestor.

BST Property - Iterative
T: O(h)S: O(1)

Use BST property: go left if both smaller, go right if both larger, else root is LCA.

BST Property - Recursive
T: O(h)S: O(h)

Same BST property implemented recursively.

Common Mistakes

Not using the BST property (treating it as a regular binary tree)

Forgetting that the split point is the LCA

Not handling the case where one node is the ancestor of the other

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems