Description
Find the longest path between any two nodes in a binary tree, measured in edges. The path need not pass through the root. Trees are encoded as level-order arrays with null for missing children.
Solution
def diameter_of_binary_tree(root):
heights = {None: 0}
stack = [(root, False)] if root else []
best = 0
while stack:
node, ready = stack.pop()
if ready:
left, right = heights[node.left], heights[node.right]
best = max(best, left + right)
heights[node] = 1 + max(left, right)
else:
stack.append((node, True))
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
return bestExamples
Example 1
- Input
[[1,2,3,4,5]]- Output
3
The path 4-2-1-3 has three edges.
Example 2
- Input
[[1,2]]- Output
1
The two nodes share one edge.
Example 3
- Input
[[1]]- Output
0
A single node has no edges.
Approach
Use iterative postorder to compute each subtree's height. At a node, the sum of its left and right heights is the longest path passing through it. Track the largest such sum.
Time & space
O(n) time and O(n) auxiliary space for n nodes, including the height map and traversal stack.