Binary Search Tree Lowest Common Ancestor Finder

You're mid-interview at Apple, and the interviewer draws a binary search tree on the whiteboard. "Given two nodes in this BST, find their lowest common ancestor." This problem tests whether you truly understand BST properties or just memorize tree traversal patterns. On Firecode, we call it "Binary Search Tree Lowest Common Ancestor Finder," but it's also known as Lowest Common Ancestor of a Binary Search Tree on other platforms. The trick is recognizing that the BST's ordering property turns what would be an O(n) search in a general binary tree into an O(h) walk down a single path.

TL;DR

Start at the root and compare both target node values against the current node. If both are smaller, go left. If both are larger, go right. The moment they split to different sides, or one equals the current node, you've found the LCA. This runs in O(h) time and O(1) space with the iterative approach, where h is the height of the tree.

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

The lowest common ancestor problem shows up constantly at Apple, Microsoft, Meta, LinkedIn, and Bloomberg. It's a perfect litmus test: candidates who understand BST properties solve it in minutes with an elegant solution, while those who don't end up writing a general binary tree solution that's slower and more complex than necessary. Recognizing when a data structure's properties simplify the problem is exactly what interviewers are evaluating.

Understanding BSTs

A binary search tree enforces a strict ordering: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property is what makes the LCA problem tractable.

In this BST, node 6 is the root. Every node in the left subtree (0, 2, 3, 4, 5) is less than 6, and every node in the right subtree (7, 8, 9) is greater than 6. This invariant holds recursively at every level.

The Problem

Given the root of a BST and two nodes p and q, find their lowest common ancestor - the deepest node that is an ancestor of both. A node can be its own ancestor. Both p and q are guaranteed to exist in the tree, and all node values are unique.

Example 1: Nodes Split at Root

For p = 2 and q = 8, the LCA is 6 (the root). Node 2 is in the left subtree and node 8 is in the right subtree, so the root is the deepest point where their paths diverge.

Example 2: One Node is an Ancestor of the Other

For p = 2 and q = 4, the LCA is 2. Node 4 sits in the subtree of node 2, making node 2 the lowest common ancestor. A node counts as its own descendant.

Example 3: Deep Nodes in the Same Subtree

For p = 0 and q = 5, the LCA is 2. Both nodes are in the left subtree of the root, so the algorithm first moves left to node 2. From there, 0 is in the left subtree and 5 is in the right subtree, so node 2 is where they split.

Constraints

• The tree contains between 2 and 100,000 nodes
• Node values fit within a 32-bit signed integer
• All values are unique
• p and q are distinct and both present in the BST

The Key Insight

In a general binary tree, finding the LCA requires searching both subtrees for the target nodes, which takes O(n) time. But in a BST, the ordering property gives you a compass. At every node, the value tells you exactly which direction to go:

• Both targets < current node: The LCA must be in the left subtree
• Both targets > current node: The LCA must be in the right subtree
• Targets split (one left, one right): The current node is the LCA
• One target equals the current node: The current node is the LCA (a node is its own descendant)

You never search both subtrees. You walk a single path from root to the LCA, making one comparison per level.

Tracing the Algorithm

Here's how the algorithm finds the LCA of nodes 2 and 8:

At the root (6), node 2 is smaller and node 8 is larger. The targets split to different subtrees, so node 6 is the LCA. One step, done.

For a longer trace, consider LCA(0, 5):

Both 0 and 5 are less than 6, so we go left to node 2. Now 0 is less than 2 and 5 is greater than 2 - they split, so node 2 is the LCA.

And LCA(7, 9):

Both 7 and 9 are greater than 6, so we go right to node 8. Then 7 is less than 8 and 9 is greater than 8 - they split, so node 8 is the LCA.

Implementation

Java

public class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode firstNode, TreeNode secondNode) {
    TreeNode current = root;

    while (current != null) {
      if (firstNode.data < current.data && secondNode.data < current.data) {
        current = current.left;
      } else if (firstNode.data > current.data && secondNode.data > current.data) {
        current = current.right;
      } else {
        return current;
      }
    }

    return null;
  }
}

The else branch handles three cases at once: p is left and q is right, p is right and q is left, or one of them equals the current node. In all three cases, the current node is the LCA.

Python

class Solution:
    def lowest_common_ancestor(self, root: 'TreeNode', first_node: 'TreeNode', second_node: 'TreeNode') -> 'TreeNode':
        current = root

        while current:
            if first_node.data < current.data and second_node.data < current.data:
                current = current.left
            elif first_node.data > current.data and second_node.data > current.data:
                current = current.right
            else:
                return current

        return None

The logic is identical across languages. A single pointer walks down the tree, making one comparison per level. No recursion, no auxiliary data structures.

Complexity Analysis

Time: O(h)

The algorithm visits at most one node per level, walking from the root to the LCA. In a balanced BST, h = O(log n), so the algorithm runs in O(log n) time. In the worst case (a completely skewed tree where every node has only one child), h = O(n).

Space: O(1)

The iterative approach uses a single pointer variable. No recursion stack, no hash maps, no queues. This is the optimal space complexity for this problem.

BST vs General Binary Tree

The BST property gives you a significant advantage. Always mention this distinction in an interview.

Common Pitfalls

1. Writing a general binary tree solution: If the interviewer gives you a BST, don't search both subtrees. The ordering property lets you pick a single direction. Using a general LCA algorithm works but is slower and signals that you missed the BST constraint.

2. Forgetting the self-ancestor case: A node can be its own ancestor. If p = 2 and q = 4, and node 2 is on the path, node 2 is the LCA. The else branch handles this automatically because when one value equals the current node, the split condition is satisfied.

3. Using recursion when iteration suffices: The recursive solution works but uses O(h) stack space. The iterative version is cleaner and more space-efficient for this problem since you only ever walk down a single path.

4. Comparing node references instead of values: Compare node.data (or node.val), not the node objects themselves. In most interview settings, you're given node references but should use their values for BST comparisons.

Interview Tips

1. Clarify the tree type: "Is this a binary search tree or a general binary tree?" This changes the optimal solution entirely. If it's a BST, lead with the O(h) approach.

2. Walk through the split logic: Draw the BST, point to two nodes, and trace the path from root to LCA. Show the interviewer how the BST property guides each step.

3. Know both versions: Some interviewers start with BST LCA, then ask "What if it's not a BST?" Having both solutions ready is a strong signal.

4. Mention the iterative advantage: Volunteering that the iterative approach uses O(1) space versus O(h) for recursion shows depth of understanding without being asked.

5. Handle edge cases verbally: "If one node is the root, the root is always the LCA. If one node is an ancestor of the other, that ancestor is the LCA." These aren't special cases in the code, but naming them shows careful thinking.

Key Takeaways

• The BST ordering property is what makes this problem O(h) instead of O(n). At each node, you compare values and pick exactly one direction. Never search both subtrees.
• The "split point" is the LCA: the first node where one target goes left and the other goes right. This also covers the case where one target equals the current node.
• The iterative solution uses O(1) space. Prefer it over recursion unless the interviewer specifically asks for a recursive approach.
• In a balanced BST, O(h) = O(log n). In a skewed BST, O(h) = O(n). Be ready to discuss both cases.
• This problem is a gateway to harder tree problems. Master the pattern of exploiting BST ordering, and validating BSTs, finding kth smallest, and range queries all become more approachable.

Related Problems

Once you're confident with BST LCA, try these:

• Height of a Binary Tree - recursive tree traversal fundamentals
• Validate a Binary Search Tree - uses the same BST ordering property
• Kth Smallest Element in a BST - inorder traversal on a BST
• Binary Tree Level Order Traversal - BFS on trees

These are all available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. The BST traversal pattern you just learned transfers directly to dozens of other tree problems. Build the muscle memory now.

Solutions in Other Languages

JavaScript

class Solution {
  lowestCommonAncestor(root, firstNode, secondNode) {
    let current = root;

    while (current) {
      if (firstNode.data < current.data && secondNode.data < current.data) {
        current = current.left;
      } else if (firstNode.data > current.data && secondNode.data > current.data) {
        current = current.right;
      } else {
        return current;
      }
    }

    return null;
  }
}

TypeScript

class Solution {
  lowestCommonAncestor(root: TreeNode | null, firstNode: TreeNode, secondNode: TreeNode): TreeNode | null {
    let current = root;

    while (current) {
      if (firstNode.data < current.data && secondNode.data < current.data) {
        current = current.left;
      } else if (firstNode.data > current.data && secondNode.data > current.data) {
        current = current.right;
      } else {
        return current;
      }
    }

    return null;
  }
}

C++

class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* firstNode, TreeNode* secondNode) {
    TreeNode* current = root;

    while (current) {
      if (firstNode->data < current->data && secondNode->data < current->data) {
        current = current->left;
      } else if (firstNode->data > current->data && secondNode->data > current->data) {
        current = current->right;
      } else {
        return current;
      }
    }

    return nullptr;
  }
};

Go

func LowestCommonAncestor(root, firstNode, secondNode *TreeNode) *TreeNode {
    current := root

    for current != nil {
        if firstNode.Data < current.Data && secondNode.Data < current.Data {
            current = current.Left
        } else if firstNode.Data > current.Data && secondNode.Data > current.Data {
            current = current.Right
        } else {
            return current
        }
    }

    return nil
}

Scala

class Solution {
  def lowestCommonAncestor(root: TreeNode, firstNode: TreeNode, secondNode: TreeNode): TreeNode = {
    var current = root

    while (current != null) {
      if (firstNode.data < current.data && secondNode.data < current.data) {
        current = current.left
      } else if (firstNode.data > current.data && secondNode.data > current.data) {
        current = current.right
      } else {
        return current
      }
    }

    null
  }
}

Kotlin

class Solution {
  fun lowestCommonAncestor(root: TreeNode?, firstNode: TreeNode, secondNode: TreeNode): TreeNode? {
    var current = root

    while (current != null) {
      if (firstNode.data < current.data && secondNode.data < current.data) {
        current = current.left
      } else if (firstNode.data > current.data && secondNode.data > current.data) {
        current = current.right
      } else {
        return current
      }
    }

    return null
  }
}

Swift

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ firstNode: TreeNode?, _ secondNode: TreeNode?) -> TreeNode? {
        var current = root

        while current != nil {
            if firstNode!.data < current!.data && secondNode!.data < current!.data {
                current = current!.left
            } else if firstNode!.data > current!.data && secondNode!.data > current!.data {
                current = current!.right
            } else {
                return current
            }
        }

        return nil
    }
}

Rust

The Rust solution uses a recursive helper due to ownership semantics. The pattern is the same: compare values, pick a direction, return when they split.

impl Solution {
    pub fn lowest_common_ancestor(
        &self,
        root: Option<Box<TreeNode>>,
        first_node: Option<Box<TreeNode>>,
        second_node: Option<Box<TreeNode>>,
    ) -> Option<Box<TreeNode>> {
        let first_val = first_node.as_ref().unwrap().data;
        let second_val = second_node.as_ref().unwrap().data;
        Self::find_lca(root, first_val, second_val)
    }

    fn find_lca(node: Option<Box<TreeNode>>, first_val: i32, second_val: i32) -> Option<Box<TreeNode>> {
        let current = node?;

        if first_val < current.data && second_val < current.data {
            Self::find_lca(current.left, first_val, second_val)
        } else if first_val > current.data && second_val > current.data {
            Self::find_lca(current.right, first_val, second_val)
        } else {
            Some(current)
        }
    }
}

C#

public class Solution {
    public TreeNode? LowestCommonAncestor(TreeNode? root, TreeNode firstNode, TreeNode secondNode) {
        var current = root;

        while (current != null) {
            if (firstNode.data < current.data && secondNode.data < current.data) {
                current = current.left;
            } else if (firstNode.data > current.data && secondNode.data > current.data) {
                current = current.right;
            } else {
                return current;
            }
        }

        return null;
    }
}

Dart

class Solution {
  TreeNode? lowestCommonAncestor(TreeNode? root, TreeNode firstNode, TreeNode secondNode) {
    TreeNode? current = root;

    while (current != null) {
      if (firstNode.data < current.data && secondNode.data < current.data) {
        current = current.left;
      } else if (firstNode.data > current.data && secondNode.data > current.data) {
        current = current.right;
      } else {
        return current;
      }
    }

    return null;
  }
}

PHP

class Solution {
    public function lowestCommonAncestor(?TreeNode $root, ?TreeNode $firstNode, ?TreeNode $secondNode): ?TreeNode {
        $current = $root;

        while ($current !== null) {
            if ($firstNode->data < $current->data && $secondNode->data < $current->data) {
                $current = $current->left;
            } elseif ($firstNode->data > $current->data && $secondNode->data > $current->data) {
                $current = $current->right;
            } else {
                return $current;
            }
        }

        return null;
    }
}

Ruby

class Solution
  def lowest_common_ancestor(root, first_node, second_node)
    current = root

    while !current.nil?
      if first_node.data < current.data && second_node.data < current.data
        current = current.left
      elsif first_node.data > current.data && second_node.data > current.data
        current = current.right
      else
        return current
      end
    end

    nil
  end
end