#85 · Trees

Lowest Common Ancestor of a Binary Tree

Given a binary tree (no ordering guarantees) and two nodes p and q, find their lowest common ancestor: the deepest node that has both p and q as descendants (a node can be a descendant of itself).

MediumLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary tree and its recursion stack

Without the BST ordering you cannot decide which child to follow, so the search must cover both subtrees. A post-order recursion asks each subtree "does it contain p or q?" and combines the answers on the way back up.

Memory layout

Nodes are heap objects with two child pointers; the recursion stack holds one frame per level, so O(h) extra space (O(n) for a skewed tree).

Operation	Cost
full traversal	O(n)
stack	O(h)

Parent map / path lists

Alternative representations of "ancestors of a node": a map child → parent lets you climb from any node to the root; a root-to-node path stores the same thing top-down. Intersecting two ancestor chains gives the LCA.

Memory layout

Hash map with one entry per discovered node, or two lists of length ≤ h + 1.

Operation	Cost
build	O(n)
climb	O(h)

Why it fits

The LCA is the unique node where the two targets are found in different subtrees (or the node that is itself a target with the other below it). A subtree-return value "the target I found, or null" captures exactly that.
Each node needs only the answers of its two children, which is a textbook post-order problem solved in a single traversal.
Early-return recursion prunes: when a node is a target, nothing below it needs to be searched for the answer's correctness (as long as both targets are known to exist).

Why alternatives degrade

BST descent (compare values):: Only valid when left < node < right; in a general tree the values say nothing about which side a node is on.
Sorting nodes by depth:: Depth alone does not identify shared ancestors; you still need parent relationships.
Binary lifting / Euler tour + RMQ:: Excellent for many LCA queries after O(n log n) preprocessing, but overkill for one query.

Four approaches, from naive to production

1 · beginner

Compare the two root-to-node paths

time O(n)space O(h)

Find the path from the root to p and the path from the root to q with a backtracking DFS, then walk both paths together; the last shared node is the LCA.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    auto pathTo = [&](TreeNode* target) -> vector<TreeNode*> {
        vector<TreeNode*> path;
        function<bool(TreeNode*)> dfs = [&](TreeNode* node) -> bool {
            if (!node) return false;
            path.push_back(node);
            if (node == target || dfs(node->left) || dfs(node->right)) return true;
            path.pop_back();
            return false;
        };
        if (!dfs(root)) path.clear();
        return path;
    };
    vector<TreeNode*> a = pathTo(p);
    vector<TreeNode*> b = pathTo(q);
    if (a.empty() || b.empty()) return nullptr;
    TreeNode* lca = nullptr;
    for (size_t i = 0; i < min(a.size(), b.size()) && a[i] == b[i]; i++) lca = a[i];
    return lca;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> a = pathTo(root, p);
    List<TreeNode> b = pathTo(root, q);
    if (a == null || b == null) return null;
    TreeNode lca = null;
    for (int i = 0; i < Math.min(a.size(), b.size()) && a.get(i) == b.get(i); i++) lca = a.get(i);
    return lca;
}
private List<TreeNode> pathTo(TreeNode root, TreeNode target) {
    List<TreeNode> path = new ArrayList<>();
    return dfs(root, target, path) ? path : null;
}
private boolean dfs(TreeNode node, TreeNode target, List<TreeNode> path) {
    if (node == null) return false;
    path.add(node);
    if (node == target || dfs(node.left, target, path) || dfs(node.right, target, path)) return true;
    path.remove(path.size() - 1);
    return false;
}

def lowest_common_ancestor(root, p, q):
    def path_to(target):
        path = []
        def dfs(node):
            if not node: return False
            path.append(node)
            if node is target or dfs(node.left) or dfs(node.right): return True
            path.pop()
            return False
        return path if dfs(root) else None
    a = path_to(p)
    b = path_to(q)
    if a is None or b is None: return None
    lca = None
    for x, y in zip(a, b):
        if x is not y: break
        lca = x
    return lca

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  const pathTo = (target: TreeNode): TreeNode[] | null => {
    const path: TreeNode[] = [];
    const dfs = (node: TreeNode | null): boolean => {
      if (!node) return false;
      path.push(node);
      if (node === target || dfs(node.left) || dfs(node.right)) return true;
      path.pop();
      return false;
    };
    return dfs(root) ? path : null;
  };
  const a = pathTo(p);
  const b = pathTo(q);
  if (!a || !b) return null;
  let lca: TreeNode | null = null;
  for (let i = 0; i < Math.min(a.length, b.length) && a[i] === b[i]; i++) lca = a[i];
  return lca;
}

Flaws & bottlenecks

Two separate traversals of the tree.
Stores two paths (O(h) each, O(n) for a skewed tree).
Backtracking code with push and pop is easy to get wrong.

Interviewer cross-questions

Why does the last shared node of the paths give the LCA?

Say: Both paths start at the root; they stay identical until the point where p and q diverge, and that point is the deepest node that is an ancestor of both.

What if p is an ancestor of q?

Say: Then p's path is a prefix of q's path, and the last shared node is p itself, which is correct.

How do you do it in a single traversal?

Say: Recurse and return, from each subtree, whichever target it found: the node that receives answers from both sides is the LCA.

2 · intermediate

Parent pointers and an ancestor set

time O(n)space O(n)

Run a BFS that records each node's parent until both p and q are discovered. Then add all ancestors of p to a set and climb from q until you hit a node in the set.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    unordered_map<TreeNode*, TreeNode*> parent{{root, nullptr}};
    queue<TreeNode*> pending; pending.push(root);
    while (!parent.count(p) || !parent.count(q)) {
        TreeNode* node = pending.empty() ? nullptr : pending.front();
        if (!node) return nullptr;
        pending.pop();
        if (node->left) { parent[node->left] = node; pending.push(node->left); }
        if (node->right) { parent[node->right] = node; pending.push(node->right); }
    }
    unordered_set<TreeNode*> ancestors;
    for (TreeNode* cur = p; cur; cur = parent[cur]) ancestors.insert(cur);
    for (TreeNode* cur = q; cur; cur = parent[cur]) {
        if (ancestors.count(cur)) return cur;
    }
    return nullptr;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    Map<TreeNode, TreeNode> parent = new HashMap<>(); parent.put(root, null);
    Deque<TreeNode> queue = new ArrayDeque<>(); queue.add(root);
    while (!parent.containsKey(p) || !parent.containsKey(q)) {
        TreeNode node = queue.poll();
        if (node == null) return null;
        if (node.left != null) { parent.put(node.left, node); queue.add(node.left); }
        if (node.right != null) { parent.put(node.right, node); queue.add(node.right); }
    }
    Set<TreeNode> ancestors = new HashSet<>();
    for (TreeNode cur = p; cur != null; cur = parent.get(cur)) ancestors.add(cur);
    for (TreeNode cur = q; cur != null; cur = parent.get(cur)) {
        if (ancestors.contains(cur)) return cur;
    }
    return null;
}

def lowest_common_ancestor(root, p, q):
    if not root: return None
    parent = {root: None}
    queue = deque([root])
    while p not in parent or q not in parent:
        node = queue.popleft() if queue else None
        if not node: return None
        if node.left: parent[node.left] = node; queue.append(node.left)
        if node.right: parent[node.right] = node; queue.append(node.right)
    ancestors = set()
    cur = p
    while cur: ancestors.add(cur); cur = parent.get(cur)
    cur = q
    while cur:
        if cur in ancestors: return cur
        cur = parent.get(cur)
    return None

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  const parent = new Map<TreeNode, TreeNode | null>([[root, null]]);
  const queue: TreeNode[] = [root];
  while (!parent.has(p) || !parent.has(q)) {
    const node = queue.shift();
    if (!node) return null;
    if (node.left) { parent.set(node.left, node); queue.push(node.left); }
    if (node.right) { parent.set(node.right, node); queue.push(node.right); }
  }
  const ancestors = new Set<TreeNode>();
  for (let cur: TreeNode | null = p; cur; cur = parent.get(cur) ?? null) ancestors.add(cur);
  for (let cur: TreeNode | null = q; cur; cur = parent.get(cur) ?? null) {
    if (ancestors.has(cur)) return cur;
  }
  return null;
}

Flaws & bottlenecks

Needs a parent map with up to n entries plus a queue and an ancestor set.
More memory than the recursive solution.
BFS may visit most of the tree before both nodes are seen.

Interviewer cross-questions

Why does the first ancestor of q that is also an ancestor of p have to be the LOWEST one?

Say: Climbing from q visits q's ancestors from deepest to shallowest, so the first hit is the deepest common one.

Can you avoid the set?

Say: Yes: compute depths and lift the deeper node to the other's level, then move both up together until they meet (O(1) extra beyond the parent map).

When is a parent map the better choice?

Say: When the same tree is queried many times, or nodes already have parent links; for a one-off query recursion is simpler.

3 · advanced

Recursion: return the target you found

time O(n)space O(h)

Return the node if it is null, p or q. Otherwise search both subtrees: if both return something, the current node is the LCA; if only one does, pass its result up.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || 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;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || 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;
}

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q: return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right: return root
    return left or right

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || 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 ?? right;
}

Flaws & bottlenecks

Recursion depth is O(n) for a skewed tree, which can overflow the call stack.
Assumes both p and q are in the tree; if one is missing it returns the one that exists, which is wrong.
Compares nodes by identity, so duplicate values are fine but copies of nodes are not.

Interviewer cross-questions

Why can it return as soon as it meets p or q?

Say: If the other target is below, this node is the ancestor. If it is not below, then (under the assumption that both exist) it is somewhere else and this node is simply the only target found on this branch.

What does it return if q is not in the tree?

Say: It returns p (the only one found), which is not an LCA: the early return hides the missing node.

How would you make it iterative?

Say: Use an explicit stack with a post-order state, or the parent-map version; this avoids recursion depth limits.

4 · expert

Validated post-order (handles missing nodes)

time O(n)space O(h)

Do the same recursion but visit every node and set foundP / foundQ flags; at the end return the candidate only if both flags are true.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    bool foundP = false, foundQ = false;
    function<TreeNode*(TreeNode*)> dfs = [&](TreeNode* node) -> TreeNode* {
        if (!node) return nullptr;
        TreeNode* left = dfs(node->left);
        TreeNode* right = dfs(node->right);
        if (node == p) foundP = true;
        if (node == q) foundQ = true;
        if (node == p || node == q) return node;
        if (left && right) return node;
        return left ? left : right;
    };
    TreeNode* lca = dfs(root);
    return foundP && foundQ ? lca : nullptr;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    boolean[] found = new boolean[2];
    TreeNode lca = dfs(root, p, q, found);
    return found[0] && found[1] ? lca : null;
}
private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q, boolean[] found) {
    if (node == null) return null;
    TreeNode left = dfs(node.left, p, q, found);
    TreeNode right = dfs(node.right, p, q, found);
    if (node == p) found[0] = true;
    if (node == q) found[1] = true;
    if (node == p || node == q) return node;
    if (left != null && right != null) return node;
    return left != null ? left : right;
}

def lowest_common_ancestor(root, p, q):
    found_p = found_q = False
    def dfs(node):
        nonlocal found_p, found_q
        if not node: return None
        left = dfs(node.left)
        right = dfs(node.right)
        if node is p: found_p = True
        if node is q: found_q = True
        if node is p or node is q: return node
        if left and right: return node
        return left or right
    lca = dfs(root)
    return lca if found_p and found_q else None

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  let foundP = false, foundQ = false;
  const dfs = (node: TreeNode | null): TreeNode | null => {
    if (!node) return null;
    const left = dfs(node.left);
    const right = dfs(node.right);
    if (node === p) foundP = true;
    if (node === q) foundQ = true;
    if (node === p || node === q) return node;
    if (left && right) return node;
    return left ?? right;
  };
  const lca = dfs(root);
  return foundP && foundQ ? lca : null;
}

Flaws & bottlenecks

Always visits all n nodes: no early exit when both targets are found early.
Still recursive; use an iterative post-order for degenerate (very deep) trees.
Slightly more code than the classic solution.

Interviewer cross-questions

Why visit the subtrees before checking the node itself?

Say: If the node is p, its subtree may still hold q. Visiting the children first lets the flags see q even when the node returns early.

What is returned if one target is not in the tree?

Say: null: the flags catch it, so the function never returns a misleading ancestor.

How would you handle a tree with 10⁶ nodes in a chain?

Say: Convert to iterative post-order with an explicit stack (or build parent links), because recursion depth would exceed the call stack.

Synchronized code walkthrough

Showing: Compare the two root-to-node paths — shares the player above; click any step to jump.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    auto pathTo = [&](TreeNode* target) -> vector<TreeNode*> {
        vector<TreeNode*> path;
        function<bool(TreeNode*)> dfs = [&](TreeNode* node) -> bool {
            if (!node) return false;
            path.push_back(node);
            if (node == target || dfs(node->left) || dfs(node->right)) return true;
            path.pop_back();
            return false;
        };
        if (!dfs(root)) path.clear();
        return path;
    };
    vector<TreeNode*> a = pathTo(p);
    vector<TreeNode*> b = pathTo(q);
    if (a.empty() || b.empty()) return nullptr;
    TreeNode* lca = nullptr;
    for (size_t i = 0; i < min(a.size(), b.size()) && a[i] == b[i]; i++) lca = a[i];
    return lca;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> a = pathTo(root, p);
    List<TreeNode> b = pathTo(root, q);
    if (a == null || b == null) return null;
    TreeNode lca = null;
    for (int i = 0; i < Math.min(a.size(), b.size()) && a.get(i) == b.get(i); i++) lca = a.get(i);
    return lca;
}
private List<TreeNode> pathTo(TreeNode root, TreeNode target) {
    List<TreeNode> path = new ArrayList<>();
    return dfs(root, target, path) ? path : null;
}
private boolean dfs(TreeNode node, TreeNode target, List<TreeNode> path) {
    if (node == null) return false;
    path.add(node);
    if (node == target || dfs(node.left, target, path) || dfs(node.right, target, path)) return true;
    path.remove(path.size() - 1);
    return false;
}

def lowest_common_ancestor(root, p, q):
    def path_to(target):
        path = []
        def dfs(node):
            if not node: return False
            path.append(node)
            if node is target or dfs(node.left) or dfs(node.right): return True
            path.pop()
            return False
        return path if dfs(root) else None
    a = path_to(p)
    b = path_to(q)
    if a is None or b is None: return None
    lca = None
    for x, y in zip(a, b):
        if x is not y: break
        lca = x
    return lca

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  const pathTo = (target: TreeNode): TreeNode[] | null => {
    const path: TreeNode[] = [];
    const dfs = (node: TreeNode | null): boolean => {
      if (!node) return false;
      path.push(node);
      if (node === target || dfs(node.left) || dfs(node.right)) return true;
      path.pop();
      return false;
    };
    return dfs(root) ? path : null;
  };
  const a = pathTo(p);
  const b = pathTo(q);
  if (!a || !b) return null;
  let lca: TreeNode | null = null;
  for (let i = 0; i < Math.min(a.length, b.length) && a[i] === b[i]; i++) lca = a[i];
  return lca;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    unordered_map<TreeNode*, TreeNode*> parent{{root, nullptr}};
    queue<TreeNode*> pending; pending.push(root);
    while (!parent.count(p) || !parent.count(q)) {
        TreeNode* node = pending.empty() ? nullptr : pending.front();
        if (!node) return nullptr;
        pending.pop();
        if (node->left) { parent[node->left] = node; pending.push(node->left); }
        if (node->right) { parent[node->right] = node; pending.push(node->right); }
    }
    unordered_set<TreeNode*> ancestors;
    for (TreeNode* cur = p; cur; cur = parent[cur]) ancestors.insert(cur);
    for (TreeNode* cur = q; cur; cur = parent[cur]) {
        if (ancestors.count(cur)) return cur;
    }
    return nullptr;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    Map<TreeNode, TreeNode> parent = new HashMap<>(); parent.put(root, null);
    Deque<TreeNode> queue = new ArrayDeque<>(); queue.add(root);
    while (!parent.containsKey(p) || !parent.containsKey(q)) {
        TreeNode node = queue.poll();
        if (node == null) return null;
        if (node.left != null) { parent.put(node.left, node); queue.add(node.left); }
        if (node.right != null) { parent.put(node.right, node); queue.add(node.right); }
    }
    Set<TreeNode> ancestors = new HashSet<>();
    for (TreeNode cur = p; cur != null; cur = parent.get(cur)) ancestors.add(cur);
    for (TreeNode cur = q; cur != null; cur = parent.get(cur)) {
        if (ancestors.contains(cur)) return cur;
    }
    return null;
}

def lowest_common_ancestor(root, p, q):
    if not root: return None
    parent = {root: None}
    queue = deque([root])
    while p not in parent or q not in parent:
        node = queue.popleft() if queue else None
        if not node: return None
        if node.left: parent[node.left] = node; queue.append(node.left)
        if node.right: parent[node.right] = node; queue.append(node.right)
    ancestors = set()
    cur = p
    while cur: ancestors.add(cur); cur = parent.get(cur)
    cur = q
    while cur:
        if cur in ancestors: return cur
        cur = parent.get(cur)
    return None

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  const parent = new Map<TreeNode, TreeNode | null>([[root, null]]);
  const queue: TreeNode[] = [root];
  while (!parent.has(p) || !parent.has(q)) {
    const node = queue.shift();
    if (!node) return null;
    if (node.left) { parent.set(node.left, node); queue.push(node.left); }
    if (node.right) { parent.set(node.right, node); queue.push(node.right); }
  }
  const ancestors = new Set<TreeNode>();
  for (let cur: TreeNode | null = p; cur; cur = parent.get(cur) ?? null) ancestors.add(cur);
  for (let cur: TreeNode | null = q; cur; cur = parent.get(cur) ?? null) {
    if (ancestors.has(cur)) return cur;
  }
  return null;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || 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;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || 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;
}

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q: return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right: return root
    return left or right

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || 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 ?? right;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    bool foundP = false, foundQ = false;
    function<TreeNode*(TreeNode*)> dfs = [&](TreeNode* node) -> TreeNode* {
        if (!node) return nullptr;
        TreeNode* left = dfs(node->left);
        TreeNode* right = dfs(node->right);
        if (node == p) foundP = true;
        if (node == q) foundQ = true;
        if (node == p || node == q) return node;
        if (left && right) return node;
        return left ? left : right;
    };
    TreeNode* lca = dfs(root);
    return foundP && foundQ ? lca : nullptr;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    boolean[] found = new boolean[2];
    TreeNode lca = dfs(root, p, q, found);
    return found[0] && found[1] ? lca : null;
}
private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q, boolean[] found) {
    if (node == null) return null;
    TreeNode left = dfs(node.left, p, q, found);
    TreeNode right = dfs(node.right, p, q, found);
    if (node == p) found[0] = true;
    if (node == q) found[1] = true;
    if (node == p || node == q) return node;
    if (left != null && right != null) return node;
    return left != null ? left : right;
}

def lowest_common_ancestor(root, p, q):
    found_p = found_q = False
    def dfs(node):
        nonlocal found_p, found_q
        if not node: return None
        left = dfs(node.left)
        right = dfs(node.right)
        if node is p: found_p = True
        if node is q: found_q = True
        if node is p or node is q: return node
        if left and right: return node
        return left or right
    lca = dfs(root)
    return lca if found_p and found_q else None

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  let foundP = false, foundQ = false;
  const dfs = (node: TreeNode | null): TreeNode | null => {
    if (!node) return null;
    const left = dfs(node.left);
    const right = dfs(node.right);
    if (node === p) foundP = true;
    if (node === q) foundQ = true;
    if (node === p || node === q) return node;
    if (left && right) return node;
    return left ?? right;
  };
  const lca = dfs(root);
  return foundP && foundQ ? lca : null;
}