Easy Post-order Height Trees
In plain English: Find the longest path between any two nodes in a binary tree, counted in edges.
The diameter through any node = left_height + right_height. Compute heights bottom-up (post-order) and track the maximum diameter seen. The answer might not pass through the root.
Prompt
Given the root of a binary tree, return the length of the diameter (the longest path between any two nodes, measured in edges).
Try to write it from scratch before scrolling down.
Solution
def diameter_of_binary_tree(root):
diameter = 0
# post-order: compute subtree heights bottom-up so parent can combine them
def height(node):
nonlocal diameter
if not node:
return 0
left = height(node.left)
right = height(node.right)
# longest path through this node is left_height + right_height
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameter
# Test: tree [1,2,3,4,5] (2 is left child of 1, 3 is right)
# diameter = 3 (path: 4->2->1->3 or 5->2->1->3)