LCA, distance between two nodes, and Kth ancestor in a binary tree

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}