Lowest Common Ancestor of Binary Tree

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use 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 stack	Yes (if tree very deep)	N/A	Code this approach
3. Parent Pointers + Ancestor Set	O(n)	O(n)	No (iterative)	N/A	Mention 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. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?

easy

A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.

B. Apply dynamic programming with memoization on node pairs to find longest paths.

C. Use a greedy traversal that always chooses the deeper subtree at each node.

D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

   The diameter can be found by checking the sum of left and right subtree heights at every node.

2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

   This approach visits each node once, updating the diameter with left_height + right_height.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Postorder traversal with global diameter update covers all nodes [OK]

Hint: Diameter updates at every node, not just root [OK]

Common Mistakes:

• Thinking diameter must pass through root
• Using greedy to pick deeper subtree only
• Confusing diameter with twice height

2. What is the space complexity of the Morris Preorder Traversal approach for summing root-to-leaf numbers in a binary tree with n nodes?

medium

A. O(1) because Morris traversal uses threaded binary tree links without extra stack

B. O(n) due to recursion stack in DFS

C. O(h) where h is tree height due to implicit stack usage

D. O(n) because all nodes are visited and stored temporarily

Solution

1. Step 1: Identify space usage in Morris traversal

   Morris traversal modifies tree pointers temporarily to avoid recursion or explicit stack, so no extra stack space is used.

2. Step 2: Confirm no auxiliary data structures

   Only constant extra variables (pointers and counters) are used, so space complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal is known for O(1) space by threading tree [OK]

Hint: Morris traversal avoids recursion and stack [OK]

Common Mistakes:

• Confusing recursion stack with Morris traversal
• Assuming O(h) due to tree height

3. Consider the following buggy code for checking if a binary tree is symmetric. Which line contains the subtle bug that causes incorrect results for asymmetric trees?

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return True
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

medium

A. Line 5: if t1.val != t2.val: return False

B. Line 3: if not t1 or not t2: return True

C. Line 6: return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

D. Line 8: return isMirror(root.left, root.right) if root else True

Solution

1. Step 1: Analyze base case for null nodes

   The line returns true if either t1 or t2 is null, but it should only return true if both are null.

2. Step 2: Identify that returning true when only one node is null causes false positives

   This causes asymmetric trees with missing nodes on one side to be incorrectly considered symmetric.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Base case must check both nodes null equality, not just one [OK]

Hint: Base case must return true only if both nodes are null [OK]

Common Mistakes:

• Returning true if only one node is null
• Forgetting to check node values before recursion
• Mixing left and right subtree comparisons

4. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?

hard

A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting

B. Use recursion on parent pointers to simulate traversal

C. Iteratively traverse using parent pointers and a stack to track visited nodes

D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

1. Step 1: Understand traversal constraints

   Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.

2. Step 2: Identify correct approach

   Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modified iterative approach handles parent-only trees without extra space [OK]

Hint: Parent-only trees require tracking visited nodes iteratively [OK]

Common Mistakes:

• Trying to use recursion without child pointers
• Attempting Morris traversal on parent pointers
• Using stack without tracking visited nodes

5. Suppose the binary tree nodes can have an arbitrary number of children (not just two). Which modification to the BFS-based maximum depth algorithm correctly computes the maximum depth in this scenario?

hard

A. Replace 'if node.left' and 'if node.right' checks with iterating over 'node.children' list and enqueue each child.

B. Keep the same code but only enqueue 'node.left' and 'node.right' if they exist, ignoring other children.

C. Use DFS recursion only, as BFS cannot handle nodes with more than two children.

D. Modify the code to sum depths of all children instead of taking the maximum.

Solution

1. Step 1: Understand the problem extension

   Nodes now have arbitrary children, so left/right pointers are insufficient.

2. Step 2: Modify BFS to handle multiple children

   Iterate over 'node.children' list and enqueue each child to explore all branches correctly.

3. Step 3: Evaluate other options

   Ignoring children misses nodes; DFS can work but BFS is still valid; summing depths is incorrect for max depth.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Enqueue all children ensures full traversal for max depth [OK]

Hint: Enqueue all children nodes to handle arbitrary branching [OK]

Common Mistakes:

• Ignoring extra children
• Assuming binary tree structure
• Summing depths instead of max