Lowest Common Ancestor of a BST

📋

Problem

Imagine you are navigating a family tree of employees in a company organized by hierarchy, and you want to find the closest common manager of two employees quickly.

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

The number of nodes in the tree is in the range [1, 10^5]All node values are uniquep and q are different nodes and both exist in the BST

Edge cases: p is ancestor of q → LCA is pq is ancestor of p → LCA is qp and q are on different subtrees → LCA is root or intermediate node

</>

IDE

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)function lowestCommonAncestor(root, p, q)

def lowestCommonAncestor(root, p, q):
    # Write your solution here
    pass

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // Write your solution here
    return nullptr;
}

function lowestCommonAncestor(root, p, q) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong node value (e.g., returning 2 instead of 6)Not checking if p and q lie on different sides of root; returning child node prematurely.✅ Return root if p.val <= root.val <= q.val or q.val <= root.val <= p.val.

Wrong: Returning child node when p is ancestor of q (e.g., returning 4 instead of 2)Failing to return root when root equals p or q.✅ Add condition to return root immediately if root == p or root == q.

Wrong: Returning root too early in greedy approach (e.g., returning 6 instead of 4)Stopping traversal at root without checking if both nodes lie in same subtree.✅ Traverse down subtree where both p and q lie until paths diverge.

Wrong: TLE on large inputUsing brute force path finding or full tree traversal instead of BST property exploitation.✅ Use iterative or recursive BST property exploitation to find LCA in O(h) time.

✓

Test Cases

Try testing your solution on trees with minimal nodes and ancestor-descendant pairs.

Consider tricky cases where nodes lie in the same subtree but are not direct ancestors.

Think about how to avoid full tree traversal using BST properties for large inputs.

t1_01basic

Input{"root":[6,2,8,0,4,7,9,null,null,3,5],"p":2,"q":8}

Expected6

⏱ Performance - must finish in 2000ms

The LCA of nodes 2 and 8 is 6 because 6 is the lowest node that has both 2 and 8 as descendants.

💡 Use BST properties to decide whether to go left or right from the root.

💡 Check if both p and q are smaller or greater than root to move accordingly.

💡 Return root if p and q lie on different sides or equal to root.

Why it failed: Returned wrong node value; likely failed to check if p and q lie on different sides of root. Fix by returning root when p.val <= root.val <= q.val or q.val <= root.val <= p.val.

✓ Correctly identified the lowest common ancestor using BST properties.

t1_02basic

Input{"root":[6,2,8,0,4,7,9,null,null,3,5],"p":2,"q":4}

Expected2

⏱ Performance - must finish in 2000ms

Node 2 is ancestor of 4, so LCA is 2 itself.

💡 Remember a node can be ancestor of itself in LCA definition.

💡 If root equals p or q, return root immediately.

💡 Check if p or q is ancestor of the other by comparing values.

Why it failed: Incorrectly returned a node other than p when p is ancestor of q. Fix by returning root if root equals p or q.

✓ Correctly returned ancestor node when one node is ancestor of the other.

t2_01edge

Input{"root":[1],"p":1,"q":1}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree; LCA of node with itself is the node.

💡 Consider the smallest tree possible with one node.

💡 Check if root equals p or q and return root immediately.

💡 Handle cases where p and q are the same node.

Why it failed: Failed to handle single-node tree or identical p and q nodes. Fix by returning root if root equals p or q.

✓ Correctly handled single-node tree and identical nodes.

t2_02edge

Input{"root":[2,1],"p":2,"q":1}

Expected2

⏱ Performance - must finish in 2000ms

p is ancestor of q; LCA is p itself.

💡 Check if root equals p or q and return root immediately.

💡 Use BST property to decide traversal direction.

💡 Return root if p or q matches root.

Why it failed: Incorrectly returned child node instead of ancestor when p is ancestor of q. Fix by returning root if root equals p or q.

✓ Correctly returned ancestor node when one node is ancestor of the other.

t2_03edge

Input{"root":[5,3,7,2,4,6,8],"p":2,"q":8}

Expected5

⏱ Performance - must finish in 2000ms

p and q are in different subtrees; LCA is root 5.

💡 If p and q are on different sides of root, root is LCA.

💡 Compare p.val and q.val with root.val to decide.

💡 Return root if p.val < root.val < q.val or vice versa.

Why it failed: Returned wrong node when p and q are in different subtrees. Fix by returning root when p and q lie on opposite sides.

✓ Correctly identified LCA when nodes are in different subtrees.

t3_01corner

Input{"root":[6,2,8,0,4,7,9,null,null,3,5],"p":3,"q":5}

Expected4

⏱ Performance - must finish in 2000ms

Both p and q are in left subtree of 6; LCA is 4, not 6.

💡 Do not greedily return root if p and q are both less than root.

💡 Traverse down the subtree where both nodes lie.

💡 Return the node where p and q split paths.

Why it failed: Greedy approach returned root 6 instead of correct LCA 4. Fix by traversing down subtree where both p and q lie until split point.

✓ Correctly avoided greedy trap and found correct LCA.

t3_02corner

Input{"root":[6,2,8,0,4,7,9,null,null,3,5],"p":0,"q":5}

Expected2

⏱ Performance - must finish in 2000ms

p and q are in left subtree of 6 but different branches; LCA is 2.

💡 Check if both nodes are in the same subtree or different subtrees.

💡 Return node where paths to p and q diverge.

💡 Use BST property to guide traversal.

Why it failed: Incorrectly returned root 6 instead of 2 when p and q are in same subtree but different branches. Fix by continuing traversal until paths diverge.

✓ Correctly identified LCA in same subtree with different branches.

t3_03corner

Input{"root":[2,1,3],"p":1,"q":3}

Expected2

⏱ Performance - must finish in 2000ms

p and q are leaf nodes on opposite sides; LCA is root 2.

💡 Do not confuse 0/1 constraints; each node appears once.

💡 Use BST property to find split point.

💡 Return root if p and q lie on opposite sides.

Why it failed: Mistook problem for unbounded or multiple occurrences; returned wrong node. Fix by using BST property and returning root when p and q lie on opposite sides.

✓ Correctly handled 0/1 occurrence constraint and found LCA.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1562,4688,7812,10938,14062,17188,20312,23438,26562,29688,32812,35938,39062,42188,45312,48438,51562,54688,57812,60938,64062,67188,70312,73438,76562,79688,82812,85938,89062,92188,95312,98438,781,2344,3906,5469,7031,8594,10156,11719,13281,14844,16406,17969,19531,21094,22656,24219,25781,27344,28906,30469,32031,33594,35156,36719,38281,39844,41406,42969,44531,46094,47656,49219,50781,52344,53906,55469,57031,58594,60156,61719,63281,64844,66406,67969,69531,71094,72656,74219,75781,77344,78906,80469,82031,83594,85156,86719,88281,89844,91406,92969,94531,96094,97656,99219],"p":3125,"q":85938}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced BST with 100 nodes; solution must run in O(h) time to complete within 2 seconds.

💡 Use BST properties to avoid traversing entire tree.

💡 Avoid brute force path finding; use iterative or recursive BST property exploitation.

💡 Time complexity must be O(h), where h is tree height (~log n).

Why it failed: Brute force or path comparison approach causes TLE due to O(n) or worse complexity. Fix by using BST property to find LCA in O(h) time.

✓ Solution runs in O(h) time and passes performance test.

Practice

1. Consider the following code snippet implementing the optimal iterative approach to convert a BST to a Greater Tree. Given the BST with nodes [2, 1, 3], what is the value of the root node after the function completes?

easy

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Trace reverse inorder traversal order

   Nodes visited in order: 3, 2, 1.

2. Step 2: Accumulate sums and update nodes

   acc_sum=0 initially. - Visit 3: acc_sum=3, node.val=3 - Visit 2: acc_sum=3+2=5, node.val=5 - Visit 1: acc_sum=5+1=6, node.val=6 Root node was 2, updated to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root node value after update is 5 [OK]

Hint: Reverse inorder sums nodes from largest to smallest [OK]

Common Mistakes:

• Confusing traversal order and updating nodes too early
• Off-by-one errors in accumulating sums
• Misidentifying which node is root after updates

2. Consider the following code for computing the range sum of a BST. Given the BST with root value 10, left child 5, right child 15, and range [7, 15], what is the final value of total returned by rangeSumBST?

easy

A. 25

B. 15

C. 40

D. 30

Solution

1. Step 1: Trace initial stack and total

   Start with stack=[10], total=0.

2. Step 2: Pop 10 (in range), add 10, push left(5) and right(15)

   total=10, stack=[5,15]

3. Step 3: Pop 15 (in range), add 15, push left(null) and right(null)

   total=25, stack=[5,null,null]

4. Step 4: Pop null (skip), then pop null (skip), then pop 5 (less than low=7), push right(null)

   total=25, stack=[null]

5. Step 5: Pop null (skip), stack empty, return total=25

   5 is less than low, so it is skipped and not added.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Sum includes 10 and 15 only, total=25 [OK]

Hint: Only nodes within [7,15] add to total [OK]

Common Mistakes:

• Adding nodes outside range
• Forgetting to push children after adding node

3. The following code attempts to compute the range sum of a BST using iterative DFS with pruning. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line that appends node.left when node.val < low

B. Line that pops node from stack

C. Line that adds node.val to total

D. Line that appends node.right when node.val is in range

Solution

1. Step 1: Understand pruning logic

   If node.val < low, left subtree nodes are smaller and cannot be in range, so left subtree should be skipped.

2. Step 2: Identify incorrect line

   Appending node.left when node.val < low causes unnecessary traversal of left subtree, violating pruning. It should append node.right instead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct pruning requires appending node.right only when node.val < low [OK]

Hint: Prune left subtree if node.val < low [OK]

Common Mistakes:

• Appending wrong subtree when pruning
• Forgetting to check null nodes

4. Suppose you want to balance a BST but now the tree nodes can have duplicate values and the BST property is relaxed to allow duplicates on either side. Which modification to the balancing algorithm ensures the resulting tree remains valid and balanced?

hard

A. Use preorder traversal instead of inorder to collect nodes, then rebuild.

B. Modify the middle index calculation to always pick the left middle to keep duplicates on left.

C. During inorder traversal, collect nodes preserving duplicates order, then choose middle node as root as usual.

D. Sort the collected nodes by value before rebuilding to handle duplicates properly.

Solution

1. Step 1: Understand duplicates in BST with relaxed property

   Inorder traversal still produces nodes in non-decreasing order preserving duplicates order.

2. Step 2: Rebuild balanced BST using middle node selection

   Choosing middle node as root maintains balance and respects duplicates order.

3. Step 3: Avoid sorting or preorder traversal

   Sorting is unnecessary and preorder breaks sorted order; left middle bias skews balance.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inorder traversal + middle node rebuild works with duplicates [OK]

Hint: Inorder traversal preserves duplicates order for balanced rebuild [OK]

Common Mistakes:

• Using preorder traversal losing sorted order
• Sorting nodes again causing unnecessary overhead
• Biasing middle index causing unbalanced tree

5. Suppose you want to modify the BST insertion algorithm to allow inserting duplicate values by always inserting duplicates into the left subtree. Which of the following changes to the iterative insertion code below correctly implements this behavior without breaking the BST property?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while curr:
        parent = curr
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

hard

A. Change the condition to if val <= curr.val: and insert duplicates to the left subtree.

B. Change the condition to if val < curr.val: and insert duplicates to the right subtree.

C. Always insert duplicates as new root nodes to maintain BST property.

D. Disallow duplicates by returning the original tree without insertion.

Solution

1. Step 1: Understand duplicate insertion rule

   Duplicates must go to the left subtree, so values equal to current node should be treated as less or equal.

2. Step 2: Modify comparison operator

   Changing condition to val <= curr.val ensures duplicates follow left subtree insertion path, preserving BST property.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicates inserted left by using <= comparison [OK]

Hint: Use <= to direct duplicates left, preserving BST order [OK]

Common Mistakes:

• Inserting duplicates right breaks problem requirement
• Inserting duplicates as new roots breaks BST
• Ignoring duplicates causes infinite recursion