Skip to main content

🟨 Lowest Common Ancestor of a Binary Search Tree (#235)

🔗 Problem Link​

📋 Problem Statement​

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

The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

💡 Examples​

Example 1​

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2​

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself.

🔑 Key Insights & Approach​

Core Observation: Use BST property: if both p and q are less than root, LCA is in left subtree. If both greater, LCA is in right subtree. Otherwise, root is LCA.

Why BST Properties?

  • O(h) time where h = height
  • O(1) space for iterative
  • Avoids exploring unnecessary nodes

Approaches:

  1. Iterative using BST property: O(h) time, O(1) space - optimal
  2. Recursive: O(h) time, O(h) space

Pattern: "BST Search" leveraging BST ordering property.

🐍 Solution: Python​

Approach 1: Iterative (Optimal)​

Time Complexity: O(h) | Space Complexity: O(1)

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

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        current = root

        while current:
            # Both in left subtree
            if p.val < current.val and q.val < current.val:
                current = current.left
            # Both in right subtree
            elif p.val > current.val and q.val > current.val:
                current = current.right
            else:
                # Split point found (one left, one right) or one equals current
                return current

        return None

Approach 2: Recursive​

Time Complexity: O(h) | Space Complexity: O(h)

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

🔵 Solution: Golang​

Approach: Iterative​

Time Complexity: O(h) | Space Complexity: O(1)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    current := root

    for current != nil {
        if p.Val < current.Val && q.Val < current.Val {
            current = current.Left
        } else if p.Val > current.Val && q.Val > current.Val {
            current = current.Right
        } else {
            return current
        }
    }

    return nil
}

📚 References​