LCA, distance between two nodes, and Kth ancestor in a binary tree
Problem
Three related queries on a binary tree: (1) the lowest common ancestor of two nodes; (2) the number of edges between two nodes, which is depth(a) + depth(b) − 2·depth(LCA); (3) the kth ancestor of a node, or −1 if the node is fewer than k levels deep.
Example 1
Input: root = [1, 2, 3, 4, 5, 6, 7]: dist(4, 5), dist(4, 6), 2nd ancestor of 4 Output: 2, 4, 1
Also asked as: Find LCA in a Binary tree · Find distance between 2 nodes in a Binary tree · Kth Ancestor of node in a Binary tree
Test cases
Case 1
Input: [1,2,3,4,5,6,7], 4, 5 Expected: 2
Case 2
Input: [1,2,3,4,5,6,7], 4, 6 Expected: 4
Case 3
Input: [1,2,3,4,5,6,7], 2, 4 Expected: 1
Case 4
Input: [1,2,3,4,5,6,7], 3, 3 Expected: 0
View solutionHide solution1 approach
1. LCA via post-order; distance from depths; ancestor by path
Time O(n)Space O(h)
LCA: the node where the two targets first split. Distance(a,b) = depth(a) + depth(b) − 2·depth(LCA). Kth ancestor: record the root→node path, then step back k.
function lca(root, p, q) { if (!root || root.val === p || root.val === q) return root; const L = lca(root.left, p, q); const R = lca(root.right, p, q); return L && R ? root : L || R;}function distance(root, a, b) { const depth = (n, target, d = 0) => { if (!n) return -1; if (n.val === target) return d; const l = depth(n.left, target, d + 1); return l !== -1 ? l : depth(n.right, target, d + 1); }; const anc = lca(root, a, b); return depth(anc, a, 0) + depth(anc, b, 0);}function kthAncestor(root, node, k) { const path = []; const find = (n) => { if (!n) return false; path.push(n); if (n.val === node || find(n.left) || find(n.right)) return true; path.pop(); return false; }; find(root); return path.length > k ? path[path.length - 1 - k].val : -1;}