We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lowest Common Ancestor of a Binary Search Tree

Number: 235

Difficulty: Medium

Paid? No

Companies: Meta, LinkedIn, Amazon, Bloomberg, Microsoft, Google, Apple, Yandex, X

Problem Description

Given a binary search tree (BST) and two nodes in the tree, p and q, find the lowest common ancestor (LCA) of those nodes. The LCA is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

Key Insights

  • Utilize the BST property: for any node, values in the left subtree are less and values in the right subtree are greater.
  • If both p and q have values less than the current node, the LCA must lie in the left subtree.
  • If both p and q have values greater than the current node, the LCA must lie in the right subtree.
  • When one node value is less than and the other is greater than (or equal to) the current node, the current node is the lowest common ancestor.
  • An iterative approach is efficient and uses constant extra space.

Space and Time Complexity

Time Complexity: O(h), where h is the height of the tree (O(log n) for balanced trees and O(n) in the worst-case skewed tree).
Space Complexity: O(1) with an iterative approach (O(h) if using recursion due to call stack).

Solution

The solution leverages the BST properties.
Algorithm:

  1. Start at the root node.
  2. While the current node exists:
    • If both p and q have values less than the current node’s value, move to the left child.
    • If both p and q have values greater than the current node’s value, move to the right child.
    • Otherwise, the current node is the split point where p and q diverge, so it is the lowest common ancestor.
  3. Return the current node.

This approach efficiently finds the LCA using a single traversal from the root.

Code Solutions

def lowestCommonAncestor(root, p, q):
    # Iterate until we find the lowest common ancestor
    while root:
        # If both p and q are less than the current node, move to left subtree
        if p.val < root.val and q.val < root.val:
            root = root.left
        # If both are greater, move to right subtree
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            # Found the split point; return current node as LCA
            return root
← Back to All Questions