Domain 1EasyCORE

Lowest Common Ancestor of a Binary Search Tree

The problem asks us to find the lowest common ancestor (LCA) of two given nodes in a binary search tree (BST). The LCA is defined as the lowest node that has both `p` and `q` as descendants. In a BST, for any node `n`, all values in its left subtree are less than `n.val`, and all values in its right subtree are greater than `n.val`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

235. Lowest Common Ancestor of a Binary Search Tree

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 52.1%


Problem Breakdown

The problem asks us to find the lowest common ancestor (LCA) of two given nodes in a binary search tree (BST). The LCA is defined as the lowest node that has both p and q as descendants. In a BST, for any node n, all values in its left subtree are less than n.val, and all values in its right subtree are greater than n.val.

Inputs:

  • A binary search tree (BST) represented by its root node.
  • Two nodes p and q whose LCA we need to find.

Outputs:

  • The lowest common ancestor of nodes p and q.

Implicit Constraints:

  • All node values are unique.
  • p and q exist in the BST.
  • p != q.

Intuition

A brute-force approach would involve finding the path from the root to both p and q, then comparing these paths to find their last common node. This approach has a time complexity of O(n) for each path traversal, where n is the number of nodes in the tree.

However, leveraging the properties of a BST can lead to a more efficient solution. Since we know that all values in the left subtree are less than the root and all values in the right subtree are greater, we can traverse the tree starting from the root and use these properties to determine where p and q lie relative to the current node.

Key Insight:

  • If both p and q are less than the current node’s value, then their LCA must be in the left subtree.
  • If both p and q are greater than the current node’s value, then their LCA must be in the right subtree.
  • If one of p or q is equal to the current node, or if they lie on different sides of the current node, then the current node is their LCA.

Approach

  1. Start at the root of the BST.
  2. Compare the values of p, q, and the current node:
    • If both p and q are less than the current node’s value, move to the left child.
    • If both p and q are greater than the current node’s value, move to the right child.
    • Otherwise, the current node is the LCA.
  3. Repeat until the LCA is found.

This approach leverages the BST properties to efficiently find the LCA with a time complexity of O(h), where h is the height of the tree.

Complexity Analysis

  • Time Complexity: O(h), where h is the height of the tree. In the worst case, this can be O(n) for a skewed tree.
  • Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    current = root
    
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

# Example usage:
# Construct the BST from the example
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)

# Find LCA of nodes 2 and 8
print(lowestCommonAncestor(root, root.left, root.right).val)  # Output: 6

# Find LCA of nodes 2 and 4
print(lowestCommonAncestor(root, root.left, root.left.right).val)  # Output: 2

# Find LCA of nodes 2 and 1
print(lowestCommonAncestor(root, root.left, root.left.left).val)  # Output: 2

Edge Cases Handled

  • Root is one of the nodes (p or q): The algorithm correctly identifies the root as the LCA.
  • Nodes are on different sides of the tree: The algorithm finds the first node where the paths diverge, which is the LCA.
  • Skewed Tree (worst case): Although the time complexity is O(n), the approach still works efficiently for such cases.