Bird
Raised Fist0
Interview Preptree-dfsmediumFacebookAmazonMicrosoftGoogleBloomberg

Lowest Common Ancestor of Binary Tree

Choose your preparation mode4 modes available
🎯
Lowest Common Ancestor of Binary Tree
mediumTREEFacebookAmazonMicrosoft

Imagine a family tree where you want to find the closest common ancestor of two relatives. This problem models that scenario in a binary tree structure.

💡 This problem requires understanding how to traverse trees and combine information from subtrees. Beginners often struggle because it involves thinking recursively about how to propagate information up the tree and handle multiple cases.
📋
Problem Statement

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

The number of nodes in the tree is in the range [1, 10^5].All node values are unique.p and q are different and both exist in the tree.
💡
Example
Input"root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1"
Output3

The LCA of nodes 5 and 1 is 3 because 3 is the lowest node that has both 5 and 1 as descendants.

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

Node 5 is an ancestor of node 4, so the LCA is 5 itself.

  • p is the root and q is a leaf → output is root
  • p and q are the same node → output is that node
  • p and q are on different subtrees → output is their common ancestor
  • Tree with only one node → p and q are that node → output is that node
⚠️
Common Mistakes
Not handling the case when one node is ancestor of the other

Returns wrong LCA or null

✅ Check if current node is p or q and return it immediately

Using path comparison but forgetting to backtrack path correctly

Incorrect paths stored, wrong LCA returned

✅ Pop node from path when backtracking if target not found

Assuming nodes have parent pointers when they don't

Code fails or infinite loops

✅ Build parent map explicitly if needed

Not considering null nodes in recursion base cases

Runtime errors or incorrect results

✅ Always check for null before accessing node properties

Comparing nodes by value instead of by reference

Wrong LCA if values are same but nodes different

✅ Compare nodes by identity, not just value

🧠
Brute Force (Check Paths and Compare)
💡 This approach exists to build intuition by explicitly finding paths from root to each node 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.

Algorithm

  1. Traverse the tree to find the path from root to node p and store it.
  2. Traverse the tree to find the path from root to node q and store it.
  3. Compare the two paths node by node until they differ.
  4. The last common node before the difference is the LCA.
💡 This algorithm is easy to visualize but requires extra space and repeated traversals, which can be inefficient for large trees.
</>
Code
from typing import Optional, List

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

def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    def find_path(node: Optional[TreeNode], target: TreeNode, path: List[TreeNode]) -> bool:
        if not node:
            return False
        path.append(node)
        if node == target:
            return True
        if find_path(node.left, target, path) or find_path(node.right, target, path):
            return True
        path.pop()
        return False

    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] if i > 0 else None

# Driver code example
if __name__ == '__main__':
    # Build example tree
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)

    p = root.left  # Node 5
    q = root.right  # Node 1
    lca = lowestCommonAncestor(root, p, q)
    print(lca.val)  # Expected output: 3
Line Notes
def find_path(node: Optional[TreeNode], target: TreeNode, path: List[TreeNode]) -> bool:Helper function to find path from root to target node
if not node:Base case: reached null node, path not found
path.append(node)Add current node to path as we traverse down
if node == target:If current node is target, path found
if find_path(node.left, target, path) or find_path(node.right, target, path):Recurse left and right to find target
path.pop()Backtrack if target not found in this path
find_path(root, p, path_p)Find path from root to p
find_path(root, q, path_q)Find path from root to 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] if i > 0 else NoneReturn last common node or None if no common ancestor
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 == target) return true;
        if (findPath(root.left, target, path) || 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 i > 0 ? pathP.get(i - 1) : null;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        TreeNode p = root.left; // 5
        TreeNode q = root.right; // 1
        TreeNode lca = sol.lowestCommonAncestor(root, p, q);
        System.out.println(lca.val); // Expected: 3
    }
}
Line Notes
public boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {Helper to find path from root to target node
if (root == null) return false;Base case: null node means path not found
path.add(root);Add current node to path
if (root == target) return true;Found target node
if (findPath(root.left, target, path) || findPath(root.right, target, path)) return true;Recurse left and right
path.remove(path.size() - 1);Backtrack if target not found here
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 i > 0 ? pathP.get(i - 1) : null;Return LCA or null
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
    if (!root) return false;
    path.push_back(root);
    if (root == target) return true;
    if (findPath(root->left, target, path) || 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 i > 0 ? pathP[i - 1] : nullptr;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    TreeNode* p = root->left; // 5
    TreeNode* q = root->right; // 1
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    cout << lca->val << endl; // Expected: 3
    return 0;
}
Line Notes
bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {Helper to find path from root to target
if (!root) return false;Base case: null node means no path
path.push_back(root);Add current node to path
if (root == target) return true;Found target node
if (findPath(root->left, target, path) || findPath(root->right, target, path)) return true;Recurse left and right
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 i > 0 ? pathP[i - 1] : nullptr;Return LCA or nullptr
class TreeNode {
    constructor(val=0, 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 === target) return true;
    if (findPath(root.left, target, path) || 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 i > 0 ? pathP[i - 1] : null;
}

// Driver code example
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);

const p = root.left; // 5
const q = root.right; // 1
const lca = lowestCommonAncestor(root, p, q);
console.log(lca.val); // Expected: 3
Line Notes
function findPath(root, target, path) {Helper to find path from root to target
if (!root) return false;Base case: null node means no path
path.push(root);Add current node to path
if (root === target) return true;Found target node
if (findPath(root.left, target, path) || findPath(root.right, target, path)) return true;Recurse left and right
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 i > 0 ? pathP[i - 1] : null;Return LCA or null
⏱
Complexity
TimeO(n) to find each path, so O(n) + O(n) = O(n)
SpaceO(n) for storing paths and recursion stack

We traverse the tree twice to find paths, each traversal can visit all nodes in worst case. Paths can be up to height of tree, O(n) in worst case.

💡 For n=20 nodes, this means up to 40 node visits and storing two paths of length up to 20.
Interview Verdict: Accepted but inefficient for large trees

This approach works but uses extra space and repeated traversals, so it's not optimal for big inputs.

🧠
Recursive DFS with Postorder Traversal
💡 This approach uses a single DFS traversal to find the LCA by returning nodes up the recursion stack. It is more efficient and elegant, teaching how to combine subtree results.

Intuition

Recursively search left and right subtrees for p and q. If both sides return non-null, current node is LCA. If one side returns non-null, propagate it up.

Algorithm

  1. If current node is null, return null.
  2. If current node is p or q, return current node.
  3. Recursively call left and right subtrees.
  4. If both left and right calls return non-null, current node is LCA.
  5. Otherwise, return non-null child or null.
💡 This algorithm cleverly uses recursion to propagate findings up, avoiding extra space for paths.
</>
Code
from typing import Optional

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

def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    if not root:
        return None
    if root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

# Driver code example
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)

    p = root.left  # Node 5
    q = root.right  # Node 1
    lca = lowestCommonAncestor(root, p, q)
    print(lca.val)  # Expected output: 3
Line Notes
if not root:Base case: reached null node, no LCA here
if root == p or root == q:If current node is p or q, return it as a potential ancestor
left = lowestCommonAncestor(root.left, p, q)Search left subtree for p or q
right = lowestCommonAncestor(root.right, p, q)Search right subtree for p or q
if left and right:If both sides found a node, current node is LCA
return rootReturn current node as LCA
return left if left else rightOtherwise propagate non-null child up
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        TreeNode p = root.left; // 5
        TreeNode q = root.right; // 1
        TreeNode lca = sol.lowestCommonAncestor(root, p, q);
        System.out.println(lca.val); // Expected: 3
    }
}
Line Notes
if (root == null) return null;Base case: no node here
if (root == p || root == q) return root;If current node is p or q, return it
TreeNode left = lowestCommonAncestor(root.left, p, q);Search left subtree
TreeNode right = lowestCommonAncestor(root.right, p, q);Search right subtree
if (left != null && right != null) return root;If both sides found nodes, current node is LCA
return left != null ? left : right;Return whichever side found a node or null
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    if (root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    TreeNode* p = root->left; // 5
    TreeNode* q = root->right; // 1
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    cout << lca->val << endl; // Expected: 3
    return 0;
}
Line Notes
if (!root) return nullptr;Base case: no node here
if (root == p || root == q) return root;Return node if it matches p or q
TreeNode* left = lowestCommonAncestor(root->left, p, q);Search left subtree
TreeNode* right = lowestCommonAncestor(root->right, p, q);Search right subtree
if (left && right) return root;If both sides found nodes, current node is LCA
return left ? left : right;Return whichever side found a node or nullptr
class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(root, p, q) {
    if (!root) return null;
    if (root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

// Driver code example
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);

const p = root.left; // 5
const q = root.right; // 1
const lca = lowestCommonAncestor(root, p, q);
console.log(lca.val); // Expected: 3
Line Notes
if (!root) return null;Base case: no node here
if (root === p || root === q) return root;Return node if it matches p or q
const left = lowestCommonAncestor(root.left, p, q);Search left subtree
const right = lowestCommonAncestor(root.right, p, q);Search right subtree
if (left && right) return root;If both sides found nodes, current node is LCA
return left ? left : right;Return whichever side found a node or null
⏱
Complexity
TimeO(n) single traversal
SpaceO(h) recursion stack where h is tree height

Each node is visited once. The recursion stack depth is at most the height of the tree.

💡 For n=20 nodes in a balanced tree, height ~5, so max 5 recursive calls on stack.
Interview Verdict: Accepted and optimal for this problem

This approach is efficient and elegant, the preferred solution in interviews.

🧠
Parent Pointers + Ancestor Set
💡 This approach uses extra memory to store parent pointers for each node, then walks ancestors of p and q to find the LCA. It is useful when parent pointers are available or can be preprocessed.

Intuition

Record each node's parent in a map. Then collect all ancestors of p in a set. Walk ancestors of q upwards until one is in p's ancestor set.

Algorithm

  1. Traverse the tree to build a map from node to its parent.
  2. Create a set of all ancestors of p by moving up using parent pointers.
  3. Move up from q using parent pointers until a node is found in p's ancestor set.
  4. Return that node as the LCA.
💡 This approach trades extra space for simpler ancestor lookup, useful in some interview scenarios.
</>
Code
from typing import Optional

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

def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

# Driver code example
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)

    p = root.left  # Node 5
    q = root.right  # Node 1
    lca = lowestCommonAncestor(root, p, q)
    print(lca.val)  # Expected output: 3
Line Notes
parent = {root: None}Initialize parent map with root having no parent
while p not in parent or q not in parent:Build parent map until both p and q are found
parent[node.left] = nodeRecord parent of left child
parent[node.right] = nodeRecord parent of right child
ancestors = set()Create set to store ancestors of p
while p:Add all ancestors of p to set
while q not in ancestors:Move up from q until common ancestor found
return qReturn the LCA node
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        parent.put(root, null);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }

        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        while (!ancestors.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        TreeNode p = root.left; // 5
        TreeNode q = root.right; // 1
        TreeNode lca = sol.lowestCommonAncestor(root, p, q);
        System.out.println(lca.val); // Expected: 3
    }
}
Line Notes
Map<TreeNode, TreeNode> parent = new HashMap<>();Map to store parent pointers
parent.put(root, null);Root has no parent
while (!parent.containsKey(p) || !parent.containsKey(q)) {Build parent map until p and q found
parent.put(node.left, node);Record parent of left child
parent.put(node.right, node);Record parent of right child
Set<TreeNode> ancestors = new HashSet<>();Set to store ancestors of p
while (p != null) {Add all ancestors of p
while (!ancestors.contains(q)) {Move up from q until common ancestor found
return q;Return LCA
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    unordered_map<TreeNode*, TreeNode*> parent;
    parent[root] = nullptr;
    stack<TreeNode*> stk;
    stk.push(root);
    while (parent.find(p) == parent.end() || parent.find(q) == parent.end()) {
        TreeNode* node = stk.top();
        stk.pop();
        if (node->left) {
            parent[node->left] = node;
            stk.push(node->left);
        }
        if (node->right) {
            parent[node->right] = node;
            stk.push(node->right);
        }
    }

    unordered_set<TreeNode*> ancestors;
    while (p) {
        ancestors.insert(p);
        p = parent[p];
    }
    while (ancestors.find(q) == ancestors.end()) {
        q = parent[q];
    }
    return q;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    TreeNode* p = root->left; // 5
    TreeNode* q = root->right; // 1
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    cout << lca->val << endl; // Expected: 3
    return 0;
}
Line Notes
unordered_map<TreeNode*, TreeNode*> parent;Map to store parent pointers
parent[root] = nullptr;Root has no parent
while (parent.find(p) == parent.end() || parent.find(q) == parent.end()) {Build parent map until p and q found
parent[node->left] = node;Record parent of left child
parent[node->right] = node;Record parent of right child
unordered_set<TreeNode*> ancestors;Set to store ancestors of p
while (p) {Add all ancestors of p
while (ancestors.find(q) == ancestors.end()) {Move up from q until common ancestor found
return q;Return LCA
class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(root, p, q) {
    const parent = new Map();
    parent.set(root, null);
    const stack = [root];
    while (!parent.has(p) || !parent.has(q)) {
        const node = stack.pop();
        if (node.left) {
            parent.set(node.left, node);
            stack.push(node.left);
        }
        if (node.right) {
            parent.set(node.right, node);
            stack.push(node.right);
        }
    }

    const ancestors = new Set();
    while (p) {
        ancestors.add(p);
        p = parent.get(p);
    }
    while (!ancestors.has(q)) {
        q = parent.get(q);
    }
    return q;
}

// Driver code example
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);

const p = root.left; // 5
const q = root.right; // 1
const lca = lowestCommonAncestor(root, p, q);
console.log(lca.val); // Expected: 3
Line Notes
const parent = new Map();Map to store parent pointers
parent.set(root, null);Root has no parent
while (!parent.has(p) || !parent.has(q)) {Build parent map until p and q found
parent.set(node.left, node);Record parent of left child
parent.set(node.right, node);Record parent of right child
const ancestors = new Set();Set to store ancestors of p
while (p) {Add all ancestors of p
while (!ancestors.has(q)) {Move up from q until common ancestor found
return q;Return LCA
⏱
Complexity
TimeO(n) to build parent map + O(h) to find LCA
SpaceO(n) for parent map and ancestor set

We visit each node once to build parent pointers. Then walk ancestors up to height h.

💡 For n=20 nodes, building parent map is 20 steps, walking ancestors is up to tree height ~5.
Interview Verdict: Accepted, useful if parent pointers needed

This approach is practical when parent pointers are available or preprocessing is allowed, but uses extra memory.

📊
All Approaches - One-Glance Tradeoffs
💡 In 95% of interviews, code the recursive DFS approach (Approach 2) because it is optimal and elegant.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Path Comparison)O(n)O(n)Yes (deep recursion in path finding)Yes (paths explicitly stored)Mention only - never code due to inefficiency
2. Recursive DFS (Postorder)O(n)O(h) recursion stackYes (if tree very deep)N/ACode this approach
3. Parent Pointers + Ancestor SetO(n)O(n)No (iterative)N/AMention if parent pointers allowed or preprocessing possible
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the optimal recursive DFS solution. Finally, discuss alternative approaches if time permits.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach of finding paths and comparing them.Explain the recursive DFS approach that finds LCA in one traversal.Mention the parent pointer approach if relevant.Write clean, tested code for the recursive DFS solution.Test with example and edge cases.

Time Allocation

Clarify: 2min → Approach explanation: 5min → Code: 10min → Testing & edge cases: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, recursion, and handling edge cases where one node is ancestor of the other or nodes are on different subtrees.

Common Follow-ups

  • What if nodes might not exist in the tree? → Add checks during traversal.
  • How to find LCA in a Binary Search Tree? → Use BST properties to optimize.
💡 These follow-ups test your ability to adapt the solution to variations and optimize using problem-specific properties.
🔍
Pattern Recognition

When to Use

1) Problem involves finding common ancestor or intersection in a tree. 2) Two nodes given, find lowest node containing both. 3) Tree traversal with recursion or parent pointers. 4) Postorder or bottom-up approach fits naturally.

Signature Phrases

lowest common ancestordescendants of a nodebinary tree nodes p and q

NOT This Pattern When

Finding LCA in a graph (not a tree) or in a DAG requires different algorithms.

Similar Problems

Lowest Common Ancestor of BST - uses BST ordering for optimizationBinary Tree Paths - uses DFS to find pathsFind Distance Between Nodes in Binary Tree - uses LCA to compute distance

Practice

(1/5)
1. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Depth-first search (DFS) with early stopping upon finding a valid path
B. Greedy traversal choosing the child with the closest value to the target sum
C. Dynamic programming with memoization of partial sums at each node
D. Breadth-first search (BFS) exploring all paths level by level

Solution

  1. Step 1: Understand the problem constraints

    The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.
  2. Step 2: Identify the best approach

    DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS explores paths fully and stops early when possible [OK]
Hint: Early stopping DFS avoids unnecessary traversal [OK]
Common Mistakes:
  • Believing greedy approach works for sums
  • Confusing BFS with DFS for path sums
2. Given a binary tree where each root-to-leaf path represents a number formed by concatenating node values, which algorithmic approach guarantees computing the sum of all such numbers efficiently without missing any path or double counting partial paths?
easy
A. Depth-first search (DFS) that accumulates the current number along the path and adds it only at leaf nodes
B. Dynamic programming that stores sums for subtrees and combines them at the root
C. Greedy traversal that sums node values at each level independently
D. Breadth-first search (BFS) that sums values of nodes at each depth and multiplies by depth

Solution

  1. Step 1: Understand problem requirements

    The problem requires summing numbers formed by concatenating node values from root to leaf, so partial paths must not be summed prematurely.
  2. Step 2: Identify correct traversal pattern

    DFS naturally explores root-to-leaf paths, allowing accumulation of the current number and summing only at leaf nodes, ensuring correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS accumulates path values correctly and sums only at leaves [OK]
Hint: Sum only at leaves during DFS traversal [OK]
Common Mistakes:
  • Summing at non-leaf nodes
  • Using BFS without path tracking
3. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?
medium
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(n h) where h is tree height

Solution

  1. Step 1: Analyze height computation calls

    Height is computed recursively for each node, and each height call traverses subtree nodes.
  2. Step 2: Calculate total calls

    For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Repeated height calls cause quadratic time [OK]
Hint: Repeated height calls cause O(n²) time [OK]
Common Mistakes:
  • Assuming height calls are O(1) leading to O(n) time
  • Confusing height with depth or tree height h
  • Thinking O(n log n) due to balanced tree assumption
4. Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:
def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                # Bug here
                current = current.right
    return result
medium
A. Line resetting predecessor.right to None is missing in the else block
B. Appending current.val before moving to left child is incorrect
C. The inner while loop condition should check predecessor.left instead of predecessor.right
D. The check for current.left being None should be after the else block

Solution

  1. Step 1: Identify missing restoration of tree structure

    In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.
  2. Step 2: Locate missing line

    The else block lacks the line predecessor.right = None, causing the threaded link to persist.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without resetting, tree remains modified after traversal [OK]
Hint: Always reset threaded links to None after use [OK]
Common Mistakes:
  • Forgetting to restore tree structure
  • Appending nodes in wrong order
  • Incorrect loop conditions
5. What is the space complexity of the optimal recursive approach to invert a binary tree, assuming the tree has n nodes and height h?
medium
A. O(n) because each node's children pointers are swapped individually
B. O(n) due to storing all nodes in a queue during traversal
C. O(1) because inversion is done in-place without extra data structures
D. O(h) due to recursion stack depth proportional to tree height

Solution

  1. Step 1: Identify auxiliary space usage in recursion

    The algorithm uses recursion, so the call stack depth is proportional to the height h of the tree.
  2. Step 2: Distinguish between in-place operations and recursion stack

    Swapping pointers is in-place (O(1) per node), but recursion stack space is O(h), not O(n).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Recursion stack dominates space, proportional to tree height h [OK]
Hint: Recursion stack space depends on tree height, not node count [OK]
Common Mistakes:
  • Confusing in-place operation with O(1) total space
  • Assuming queue-based BFS space applies to recursive DFS
  • Counting node swaps as extra space
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard