Diameter of Tree
An interactive, step-by-step visualisation of Diameter of Tree.
- Category
- Trees
- Time complexity
- O(n)
- Space complexity
- O(h)
Pseudocode
diameter(t): lh, rh ← height(t.left), height(t.right) best ← max(best, lh + rh) return 1 + max(lh, rh)
Reference implementation
best = 0
def height(t):
nonlocal best
if not t: return 0
lh, rh = height(t.l), height(t.r)
best = max(best, lh + rh)
return 1 + max(lh, rh)