Lowest Common Ancestor of a BST

🎯

Lowest Common Ancestor of a BST

mediumTREEAmazonFacebookMicrosoft

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.

💡 This problem asks you to find the lowest common ancestor (LCA) of two nodes in a BST. Beginners often struggle because they confuse BST properties with general binary trees and don't leverage the BST ordering to optimize the search.

📋

Problem Statement

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

💡

Example

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

Output6

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

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

Output2

The LCA of nodes 2 and 4 is 2 because a node can be a descendant of itself.

• p is ancestor of q → LCA is p
• q is ancestor of p → LCA is q
• p and q are on different subtrees → LCA is root or intermediate node
• Tree with only one node → LCA is that node

⚠️

Common Mistakes

Not leveraging BST properties and treating tree as general binary tree

Solution becomes inefficient and may time out on large inputs

✅ Use BST ordering to prune search space

Assuming LCA must be strictly ancestor, ignoring that node can be ancestor of itself

Incorrect LCA returned when one node is ancestor of the other

✅ Allow returning p or q if it matches current node during search

Not handling null root or empty tree cases

Code may crash or return incorrect results

✅ Add base case checks for null root

Using recursion without considering stack overflow for deep trees

Stack overflow error on very deep BSTs

✅ Use iterative approach to avoid recursion stack

Comparing node values incorrectly (e.g., using == instead of < or >)

Incorrect traversal direction, wrong LCA found

✅ Use proper comparison operators to decide subtree traversal

🧠

Brute Force (Find Paths and Compare)

💡 This approach exists to build intuition by explicitly finding paths to both nodes and then comparing them. It is straightforward but inefficient, helping beginners understand the problem structure.

Intuition

Find the path from root to p and root to q separately, then compare these paths to find the last common node, which is the LCA.

Algorithm

1. Traverse the BST from root to find the path to node p and store it.
2. Traverse the BST from root to find the path to node q and store it.
3. Compare the two paths node by node until they differ.
4. Return the last common node found in both paths as the LCA.

💡 This algorithm is easy to visualize but requires extra space and repeated traversals, which can be inefficient for large trees.

</>

Code

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

def find_path(root, target, path):
    if not root:
        return False
    path.append(root)
    if root.val == target.val:
        return True
    if (root.left and find_path(root.left, target, path)) or (root.right and find_path(root.right, target, path)):
        return True
    path.pop()
    return False

def lowestCommonAncestor(root, p, q):
    path_p = []
    path_q = []
    find_path(root, p, path_p)
    find_path(root, q, path_q)
    i = 0
    while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:
        i += 1
    return path_p[i-1]

# Example usage:
# Construct BST nodes
# root = TreeNode(6)
# ... build tree ...
# print(lowestCommonAncestor(root, p, q).val)

Line Notes

def find_path(root, target, path):Defines helper to find path from root to target node

if not root:Base case: reached leaf without finding target

path.append(root)Add current node to path as we go down

if root.val == target.val:Check if current node is target

if (root.left and find_path(root.left, target, path)) or (root.right and find_path(root.right, target, path))Recursively search left or right subtree

path.pop()Backtrack if target not found in this path

find_path(root, p, path_p)Find path to node p

find_path(root, q, path_q)Find path to node q

while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:Compare paths to find last common node

return path_p[i-1]Return the last common ancestor node

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
public class Solution {
    public boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;
        path.add(root);
        if (root.val == target.val) return true;
        if ((root.left != null && findPath(root.left, target, path)) || (root.right != null && findPath(root.right, target, path)))
            return true;
        path.remove(path.size() - 1);
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        findPath(root, p, pathP);
        findPath(root, q, pathQ);
        int i = 0;
        while (i < pathP.size() && i < pathQ.size() && pathP.get(i) == pathQ.get(i)) {
            i++;
        }
        return pathP.get(i - 1);
    }
    // main method and tree construction can be added for testing
}

Line Notes

public boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path)Helper to find path from root to target

if (root == null) return false;Base case: no node found

path.add(root);Add current node to path

if (root.val == target.val) return true;Check if current node is target

if ((root.left != null && findPath(root.left, target, path)) || (root.right != null && findPath(root.right, target, path)))Search left or right subtree recursively

path.remove(path.size() - 1);Backtrack if target not found

findPath(root, p, pathP);Find path to p

findPath(root, q, pathQ);Find path to q

while (i < pathP.size() && i < pathQ.size() && pathP.get(i) == pathQ.get(i))Compare paths to find last common node

return pathP.get(i - 1);Return LCA node

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
    if (!root) return false;
    path.push_back(root);
    if (root->val == target->val) return true;
    if ((root->left && findPath(root->left, target, path)) || (root->right && findPath(root->right, target, path)))
        return true;
    path.pop_back();
    return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode*> pathP, pathQ;
    findPath(root, p, pathP);
    findPath(root, q, pathQ);
    int i = 0;
    while (i < pathP.size() && i < pathQ.size() && pathP[i] == pathQ[i])
        i++;
    return pathP[i - 1];
}
// main function and tree construction can be added for testing

Line Notes

bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path)Helper to find path from root to target node

if (!root) return false;Base case: reached null node

path.push_back(root);Add current node to path

if (root->val == target->val) return true;Check if current node is target

if ((root->left && findPath(root->left, target, path)) || (root->right && findPath(root->right, target, path)))Recursively search left or right subtree

path.pop_back();Backtrack if target not found

findPath(root, p, pathP);Find path to p

findPath(root, q, pathQ);Find path to q

while (i < pathP.size() && i < pathQ.size() && pathP[i] == pathQ[i])Compare paths to find last common node

return pathP[i - 1];Return LCA node

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}
function findPath(root, target, path) {
    if (!root) return false;
    path.push(root);
    if (root.val === target.val) return true;
    if ((root.left && findPath(root.left, target, path)) || (root.right && findPath(root.right, target, path)))
        return true;
    path.pop();
    return false;
}
function lowestCommonAncestor(root, p, q) {
    const pathP = [];
    const pathQ = [];
    findPath(root, p, pathP);
    findPath(root, q, pathQ);
    let i = 0;
    while (i < pathP.length && i < pathQ.length && pathP[i] === pathQ[i]) {
        i++;
    }
    return pathP[i - 1];
}
// Example usage:
// let root = new TreeNode(6);
// ... build tree ...
// console.log(lowestCommonAncestor(root, p, q).val);

Line Notes

function findPath(root, target, path)Helper to find path from root to target

if (!root) return false;Base case: no node found

path.push(root);Add current node to path

if (root.val === target.val) return true;Check if current node is target

if ((root.left && findPath(root.left, target, path)) || (root.right && findPath(root.right, target, path)))Recursively search left or right subtree

path.pop();Backtrack if target not found

findPath(root, p, pathP);Find path to p

findPath(root, q, pathQ);Find path to q

while (i < pathP.length && i < pathQ.length && pathP[i] === pathQ[i])Compare paths to find last common node

return pathP[i - 1];Return LCA node

⏱

Complexity

TimeO(n) in worst case, where n is number of nodes, because we may traverse the tree twice to find paths

SpaceO(n) for storing paths and recursion stack

Finding each path can take O(n) time in worst case, and storing paths requires O(n) space. Comparing paths is O(n) as well.

💡 For n=20 nodes, this means up to 40 node visits plus storing paths, which is inefficient for large trees.

Interview Verdict: Accepted but inefficient; useful for understanding

This approach is easy to implement but not optimal. It helps beginners understand the problem before moving to better solutions.

🧠

Better (Recursive BST Property Exploitation)

💡 This approach leverages BST properties to avoid searching entire paths, improving efficiency by pruning unnecessary branches.

Intuition

Because BST nodes are ordered, if both p and q are smaller than current node, LCA lies in left subtree; if both are greater, LCA lies in right subtree; otherwise current node is LCA.

Algorithm

1. Start at root node.
2. If both p and q values are less than root's value, recurse into left subtree.
3. If both p and q values are greater than root's value, recurse into right subtree.
4. Otherwise, root is the LCA.

💡 This algorithm is more efficient because it uses BST ordering to avoid unnecessary subtree searches.

Recurrence:LCA(root) = if p.val < root.val and q.val < root.val then LCA(root.left) else if p.val > root.val and q.val > root.val then LCA(root.right) else root

</>

Code

def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    elif p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    else:
        return root

# Example usage:
# print(lowestCommonAncestor(root, p, q).val)

Line Notes

if root is None:Base case: empty subtree

if p.val < root.val and q.val < root.val:Both nodes smaller, go left

return lowestCommonAncestor(root.left, p, q)Recurse left subtree

elif p.val > root.val and q.val > root.val:Both nodes greater, go right

return lowestCommonAncestor(root.right, p, q)Recurse right subtree

else:Nodes split, current root is LCA

return rootReturn LCA node

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }
}
// main method and tree construction can be added for testing

Line Notes

if (root == null) return null;Base case: empty subtree

if (p.val < root.val && q.val < root.val)Both nodes smaller, go left

return lowestCommonAncestor(root.left, p, q);Recurse left subtree

else if (p.val > root.val && q.val > root.val)Both nodes greater, go right

return lowestCommonAncestor(root.right, p, q);Recurse right subtree

elseNodes split, current root is LCA

return root;Return LCA node

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    if (p->val < root->val && q->val < root->val) {
        return lowestCommonAncestor(root->left, p, q);
    } else if (p->val > root->val && q->val > root->val) {
        return lowestCommonAncestor(root->right, p, q);
    } else {
        return root;
    }
}
// main function and tree construction can be added for testing

Line Notes

if (!root) return nullptr;Base case: empty subtree

if (p->val < root->val && q->val < root->val)Both nodes smaller, go left

return lowestCommonAncestor(root->left, p, q);Recurse left subtree

else if (p->val > root->val && q->val > root->val)Both nodes greater, go right

return lowestCommonAncestor(root->right, p, q);Recurse right subtree

elseNodes split, current root is LCA

return root;Return LCA node

function lowestCommonAncestor(root, p, q) {
    if (!root) return null;
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }
}
// Example usage:
// console.log(lowestCommonAncestor(root, p, q).val);

Line Notes

if (!root) return null;Base case: empty subtree

if (p.val < root.val && q.val < root.val)Both nodes smaller, go left

return lowestCommonAncestor(root.left, p, q);Recurse left subtree

else if (p.val > root.val && q.val > root.val)Both nodes greater, go right

return lowestCommonAncestor(root.right, p, q);Recurse right subtree

elseNodes split, current root is LCA

return root;Return LCA node

⏱

Complexity

TimeO(h), where h is the height of the BST

SpaceO(h) due to recursion stack

Each recursive call moves down one level of the tree, so time and space depend on tree height, which is O(log n) for balanced BSTs and O(n) worst case.

💡 For a balanced BST with 20 nodes, this means about 5 steps, much faster than brute force.

Interview Verdict: Accepted and efficient for balanced BSTs

This approach is optimal for BSTs and is the standard solution interviewers expect.

🧠

Optimal (Iterative BST Property Exploitation)

💡 This approach optimizes the recursive solution by using iteration to avoid recursion overhead and stack usage.

Intuition

Use a loop to traverse the BST from root, moving left or right based on p and q values until the split point (LCA) is found.

Algorithm

1. Initialize current node as root.
2. While current node is not null:
3. If both p and q values are less than current node's value, move to left child.
4. Else if both p and q values are greater than current node's value, move to right child.
5. Else current node is LCA; break and return it.

💡 This iterative approach is straightforward and efficient, avoiding recursion stack overhead.

</>

Code

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

# Example usage:
# print(lowestCommonAncestor(root, p, q).val)

Line Notes

current = rootStart traversal from root

while current:Loop until LCA found or tree ends

if p.val < current.val and q.val < current.val:Both nodes smaller, go left

current = current.leftMove to left child

elif p.val > current.val and q.val > current.val:Both nodes greater, go right

current = current.rightMove to right child

else:Nodes split, current is LCA

return currentReturn LCA node

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode current = root;
    while (current != null) {
        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 null;
}
// main method and tree construction can be added for testing

Line Notes

TreeNode current = root;Initialize traversal pointer

while (current != null)Loop until LCA found or end

if (p.val < current.val && q.val < current.val)Both nodes smaller, go left

current = current.left;Move left

else if (p.val > current.val && q.val > current.val)Both nodes greater, go right

current = current.right;Move right

elseNodes split, current is LCA

return current;Return LCA node

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* current = root;
    while (current) {
        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 nullptr;
}
// main function and tree construction can be added for testing

Line Notes

TreeNode* current = root;Initialize traversal pointer

while (current)Loop until LCA found or end

if (p->val < current->val && q->val < current->val)Both nodes smaller, go left

current = current->left;Move left

else if (p->val > current->val && q->val > current->val)Both nodes greater, go right

current = current->right;Move right

elseNodes split, current is LCA

return current;Return LCA node

function lowestCommonAncestor(root, p, q) {
    let current = root;
    while (current) {
        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 null;
}
// Example usage:
// console.log(lowestCommonAncestor(root, p, q).val);

Line Notes

let current = root;Initialize traversal pointer

while (current)Loop until LCA found or end

if (p.val < current.val && q.val < current.val)Both nodes smaller, go left

current = current.left;Move left

else if (p.val > current.val && q.val > current.val)Both nodes greater, go right

current = current.right;Move right

elseNodes split, current is LCA

return current;Return LCA node

⏱

Complexity

TimeO(h), where h is the height of the BST

SpaceO(1) additional space

Iterative traversal visits nodes down the tree height only, no recursion stack used.

💡 For balanced BST with 20 nodes, this means about 5 steps and constant extra space.

Interview Verdict: Accepted and optimal for interviews

This is the best approach to code in interviews for this problem due to its efficiency and simplicity.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the iterative BST property approach is best for efficiency and clarity. Brute force is good for initial explanation but not for coding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Find Paths and Compare)	O(n)	O(n)	Yes (due to recursion in path finding)	Yes (paths explicitly stored)	Mention only - never code
2. Recursive BST Property Exploitation	O(h)	O(h)	Yes (deep recursion possible)	N/A	Good to explain and code if comfortable with recursion
3. Iterative BST Property Exploitation	O(h)	O(1)	No	N/A	Best approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then move to optimized BST property solutions. Practice coding and explaining each step clearly.

How to Present

Step 1: Clarify the problem and confirm BST properties and input guarantees.Step 2: Describe the brute force approach of finding paths and comparing them.Step 3: Explain how BST ordering allows pruning and leads to a recursive solution.Step 4: Present the iterative solution as the optimal approach.Step 5: Code the iterative solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of BST properties, ability to optimize from brute force, and clean coding skills. They also check if you handle edge cases and explain your approach clearly.

Common Follow-ups

• What if the tree is not a BST? → Use general binary tree LCA algorithm.
• Can you find LCA without parent pointers? → Yes, using recursion or iteration as shown.

💡 These follow-ups test your adaptability and understanding of related problems.

🔍

Pattern Recognition

When to Use

1) Input is a BST, 2) Need to find common ancestor of two nodes, 3) Nodes guaranteed to exist, 4) Want efficient search using BST ordering

Signature Phrases

'lowest common ancestor''binary search tree''both nodes are descendants''node can be descendant of itself'

NOT This Pattern When

General binary tree LCA problems without BST ordering

Similar Problems

Lowest Common Ancestor of a Binary Tree - similar but no BST propertyValidate Binary Search Tree - uses BST ordering logicFind Distance Between Nodes in BST - uses LCA to compute distance