Diameter of a Tree
Trees & BST: lesson 10 of 14
The longest path bends at exactly one node — find that node.
Lesson 10 of 14 · 6 min
Diameter of a Tree
Step 1 of 7
best0
The longest path turns at exactly one node. Find the depths first, and the bend falls out.
The Idea
The longest path between any two nodes turns at one node only. At that node the path is simply the left depth plus the right depth.
So compute depths once, bottom-up, and at every node ask "would bending here beat the best so far?" The value returned upwards is still just a depth.
Real-World Example
The longest walk through a river system runs from one headwater, down to a confluence, and back up a different tributary. Measure each branch from the sea inwards once and the answer falls out at the junctions.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def diameter(root):
best = 0
def depth(n): # returns a depth, records the best path on the way up
nonlocal best
if not n: return 0
l, r = depth(n.left), depth(n.right)
best = max(best, l + r) # the path that bends here, at n
return 1 + max(l, r) # what n reports to its own parent
depth(root)
return best
print(diameter(Node(1, Node(2, Node(4), Node(5)), Node(3)))) # 3 -- 4-2-1-3Your turn
What does this print?
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
best = 0
def depth(n):
global best
if not n: return 0
l, r = depth(n.left), depth(n.right)
best = max(best, l + r)
return 1 + max(l, r)
depth(Node(1, Node(2, Node(4, Node(6))), Node(3)))
print(best)Mini quiz
1 / 3