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 Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

3. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

4. What is the time complexity of the optimal divide-and-conquer approach to convert a sorted array of length n into a height-balanced BST, and why?

medium

A. O(n log n), because each recursive call processes half the array and builds subtrees.

B. O(n), because each element is visited exactly once to create nodes without extra overhead.

C. O(n^2), because the recursion tree has n levels and each level processes n elements.

D. O(log n), because the tree height is log n and only root nodes are created at each level.

Solution

1. Step 1: Analyze recursion calls

   The algorithm visits each element exactly once to create a TreeNode, splitting the array into halves recursively.

2. Step 2: Calculate total work

   Each element is processed once, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass over array with divide-and-conquer -> O(n) time [OK]

Hint: Each element processed once -> O(n) time [OK]

Common Mistakes:

• Confusing recursion depth with total work
• Assuming O(n log n) due to recursion

5. Suppose the BST nodes can have duplicate values and you want to compute the sum of all nodes within [low, high], including duplicates. Which modification to the iterative DFS with pruning approach correctly handles duplicates without losing efficiency?

hard

A. Use a hash set to track visited nodes to avoid double counting duplicates.

B. Remove pruning and traverse all nodes to ensure duplicates are counted.

C. Keep pruning logic unchanged since BST property guarantees duplicates are on one side only.

D. Modify pruning to include equal values on both left and right subtrees when node.val equals low or high.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can be on either left or right subtree depending on insertion rules, so pruning must consider equality carefully.

2. Step 2: Adjust pruning for duplicates

   When node.val equals low or high, both subtrees may contain duplicates within range, so both should be explored.

3. Step 3: Avoid removing pruning entirely

   Removing pruning loses efficiency; using a hash set is unnecessary as nodes are unique objects.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Pruning adjusted for equality handles duplicates efficiently [OK]

Hint: Include equal values on both sides when pruning [OK]

Common Mistakes:

• Removing pruning loses efficiency
• Assuming duplicates only on one side