Widest Node To Node Path
Problem
In a binary tree, measure the longest path between any two nodes, counting the links along it rather than the nodes. The path does not have to pass through the root, and it may bend at exactly one node on the way. Return 0 for an empty tree or a tree with a single node.
Examples
Input: tree = 1 with left child 2 having children 4 and 5, and right child 3
Output: 3
Why: the path 4, 2, 1, 3 uses three links and bends at the rootInput: tree = 1 with a single left child 2
Output: 1
Why: a single link is the only path there isInput: tree = empty
Output: 0
Why: edge case, there is no path to measureHints
0 / 3
The winning path is not always the one through the root. Try describing where any path bends, because that node tells you everything about the path.
A path bends at exactly one node, and on each side of the bend it simply dives as deep as it can. So the length at a bend is the depth of one subtree plus the depth of the other.
Compute depths from the bottom up. At each node, combine the two child depths into a candidate answer and keep the best one seen anywhere, but report upward only one more than the deeper child, since a parent can use only one side.
Solution
Every path bends at a single node and descends as far as possible on both sides, so the best path through a given node is the sum of its two subtree depths. One bottom-up traversal computes depths and, at each node, scores that sum against a running record. The value reported to the parent is different from the value scored, because a parent can only continue down one side. Each node is visited once. Time is O(n), and space is O(h) for the call stack.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def widest_path(root):
best = 0
def depth(node):
nonlocal best
if node is None:
return 0
left, right = depth(node.left), depth(node.right)
best = max(best, left + right) # the path that bends right here
return 1 + max(left, right) # a parent can only use one side
depth(root)
return best
print(widest_path(T(1, T(2, T(4), T(5)), T(3)))) # -> 3
print(widest_path(T(1, T(2)))) # -> 1
print(widest_path(None)) # -> 0Stuck on the idea rather than the code? Diameter of a Tree covers it.