PPractick

The problem

A file index is stored as a BST keyed by ID, and a sync tool often needs the lowest common ancestor of two entries. In a plain binary tree that takes a full DFS, but a BST's ordering pinpoints it with a single walk from the root. If both keys are smaller than the current node, the LCA is in the left subtree; if both are larger, it's on the right. The first node where they split (one on each side, or one of them equal to the node) is the LCA.

Example: BST [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8 → 6; p = 2, q = 4 → 2.

Function signature

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q);  // p and q are in the BST

Test cases

Input (tree, p, q)	Output	Explanation
([6,2,8,0,4,7,9,null,null,3,5], 2, 8)	6	They split at the root
([6,2,8,0,4,7,9,null,null,3,5], 2, 4)	2	A node is its own ancestor
([6,2,8,0,4,7,9,null,null,3,5], 3, 5)	4
([6,2,8,0,4,7,9,null,null,3,5], 7, 9)	8
([2, 1], 2, 1)	2

(Confirm: keys are distinct; both nodes exist; a node may be its own ancestor.)

How interviewers phrase it

• "Given a binary search tree, find the lowest common ancestor of two given nodes" (LeetCode 235).

Clarifying questions to ask

1. Is it a BST? (Yes, which enables the O(h) walk.)
2. Are both nodes guaranteed to be in the tree? (Yes.)
3. Can p be an ancestor of q? (Yes: then p is the answer.)

Follow-ups to expect

1. "Why is the split point the LCA?"
2. "Iterative or recursive?"
3. "What if p or q might be missing?"
4. "How does it compare with the binary-tree LCA?"
5. "Complexity?"

Related questions

• Insert a given node in BST Medium
• Delete a node in BST Medium
• Check if a tree is a BST or not Medium
• Construct a BST from a preorder traversal Medium
• Search in a Binary Search Tree Easy
• Floor and Ceil in a BST Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in