Diameter of Binary Tree
Asked at Roblox
Problem
Diameter of Binary Tree asks for the number of edges on the longest path between any two nodes. The path does not have to pass through the root, which is exactly the detail the interviewer is checking.
Asked At
| Company | Difficulty | |
|---|---|---|
| Roblox | Easy | View all Roblox questions → |
How to Think About It
The longest path has some highest node, where it "bends". At that node, the path length is height(left) + height(right) (heights counted in edges from that node down).
Naive approach: for every node, compute both heights from scratch — O(n²) on a skewed tree.
Key insight: compute heights bottom-up in one post-order DFS. At each node, update a global best with lh + rh, then return 1 + max(lh, rh) to the parent.
Walkthrough for [1,2,3,4,5]: node 4 and 5 return 1; node 2 sees 1 + 1 = 2 and returns 2; node 3 returns 1; root sees 2 + 1 = 3. Answer 3 (path 4-2-1-3).
Define height of a null node as 0 and of a leaf as 1 — then lh + rh counts edges on the path through the current node.
Optimal Approach
Step 1: best = 0.
Step 2: depth(node):
If node is null, return 0.
lh = depth(node.left), rh = depth(node.right).
best = max(best, lh + rh).
Return 1 + max(lh, rh).
Step 3: Call depth(root) and return best.
Time: O(n). Space: O(h) for recursion.
What Trips People Up in Real Interviews
Returning height(root.left) + height(root.right). The longest path might sit entirely inside one subtree.
Counting nodes instead of edges. The problem asks for edges, so a single node has diameter 0.
Returning the diameter from the recursive function instead of the height. The function must return height to its parent and update the diameter on the side.
Recomputing heights for every node — say explicitly that the post-order pass makes it linear.
Solution Code
def diameterOfBinaryTree(root):
best = 0
def depth(node):
nonlocal best
if not node:
return 0
lh = depth(node.left)
rh = depth(node.right)
best = max(best, lh + rh)
return 1 + max(lh, rh)
depth(root)
return bestFrequently Asked Questions
What is the Diameter of Binary Tree problem?
Diameter of Binary Tree asks for the number of edges on the longest path between any two nodes. The path does not have to pass through the root, which is exactly the detail the interviewer is checking.
How do you solve Diameter of Binary Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Diameter of Binary Tree?
Diameter of Binary Tree is asked at Roblox. It is a easy difficulty problem.
What are common mistakes on Diameter of Binary Tree?
- Returning `height(root.left) + height(root.right)`. The longest path might sit entirely inside one subtree.
- Counting nodes instead of edges. The problem asks for edges, so a single node has diameter 0.
- Returning the diameter from the recursive function instead of the height. The function must return height to its parent and update the diameter on the side.
- Recomputing heights for every node — say explicitly that the post-order pass makes it linear.