Steps between two nodes
Count the edges on the path between two nodes of a tree, by going up from each of them to their lowest common ancestor. About 14 minutes.
Up to the meeting point, then down
In a tree there is exactly one route between two nodes. It climbs from the first node to the lowest node that has both below it, their lowest common ancestor, and then descends to the second node.
So the distance is the number of edges from the ancestor down to the first node, plus the number from the ancestor down to the second. If the two nodes are the same, both are zero.
steps = depth_p + depth_q
- ancestor
- 5
The lowest common ancestor of 6 and 4 is 5.
Measure from the ancestor
Use the walk from the last step to get the ancestor. Then write a small helper that finds the depth of a value below a given node, starting at zero for that node.
Calling the helper on the ancestor, rather than on the root, gives the lengths of the two arms of the route directly. If one node is the ancestor of the other, one of the arms has length zero.
depth = 0
node = root
while node.val != v:
if v < node.val:
node = node.left
else:
node = node.right
depth += 1Node q is the parent of node p. What is the distance between them?
- A1, since the ancestor is q and the arms are 0 and 1
- B0
- C2
Show the answer
1, since the ancestor is q and the arms are 0 and 1. q is the lowest common ancestor, so the arm to q is zero.
Distance between two nodes
Given the root of a binary tree whose node values are all different, and two values p and q that both appear in the tree, return the number of edges on the path between the nodes holding p and q. If p and q are equal, the distance is 0.
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 6, q = 4 → 3
1 ≤ number of nodes ≤ 5,000 · all values are different · p and q are in the tree