Diameter of Binary Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Find the length (number of edges) of the longest path between any two nodes of the tree. It may not pass through the root.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1The longest path has a highest node. What is its length in terms of that node's left and right heights?
- Hint 2Compute heights recursively and update a best-so-far at each node.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two employees, as far apart as possible in the company: the walk between them goes up to some manager and down again. At each manager, the longest such walk through him is (depth of the deepest team on his left) + (depth of the deepest team on his right). So while each manager reports his own team's depth upward, he also quietly records this left + right total, and the biggest one over all managers is the answer.
- The obvious way
At every node compute the heights of both sides again: O(n²) for a skinny tree.
- The key insight
One height function visits each node once. At a node with left height L and right height R, the longest path bending here has L + R edges: update the global best. Return 1 + max(L, R) to the parent as this node's height.
- The algorithm
- best = 0. A height function: empty spot has height 0.
- At a node get the left height L and the right height R.
- best = max(best, L + R).
- Return 1 + max(L, R). The answer is best.
Watch it run
Exampletree = [1, 2, 3, 4, 5]
Leaves 4 and 5 have height 1 (L = R = 0, bend length 0).
best 0
Where people slip
- The diameter counts edges, which equals left height + right height when heights count nodes.
- The path need not pass through the root; that is why we check every node.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def diameter_of_binary_tree(root):
best = 0
def height(node):
nonlocal best
if node is None:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right) # the longest path that bends at this node
return 1 + max(left, right)
height(root)
return bestNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.