Easy Recursive Max Advanced Trees
In plain English: Find the longest path between any two nodes in a binary tree, measured in edges.
At each node, the longest path through it is left_height + right_height. Track the global maximum while computing heights bottom-up.
Prompt
Find the diameter of a binary tree — the length of the longest path between any two nodes (in edges).
Try to write it from scratch before scrolling down.
Solution
def diameter_of_binary_tree(root):
diameter = [0]
def height(node):
if not node:
return 0
lh = height(node.left)
rh = height(node.right)
diameter[0] = max(diameter[0], lh + rh) # path through this node
return 1 + max(lh, rh)
height(root)
return diameter[0]
# Test: tree [1,2,3,4,5] => diameter = 3 (path 4->2->1->3)