We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given a binary tree, return the length of its diameter: the number of edges on the longest path between any two nodes.
The path does not have to pass through the root.
The tree is given as a level-order array with explicit nulls, where the children of index i sit at 2i + 1 and 2i + 2. An empty array is an empty tree.
An easy trees problem, graded against 6 test cases (3 of them hidden).
Recursive traversal of binary trees and BSTs - depth, validation, and path problems.
Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.
More Trees problems →The key reframing: for each individual node, the longest path passing *through* that node is `leftHeight + rightHeight` measured in edges. The diameter is the maximum of that quantity over all nodes.
So one post-order traversal does it. Each call computes its children's heights, updates a running maximum with their sum, and returns `1 + max(left, right)` for its own parent. The two quantities are different - what you return is not what you track - and conflating them is the usual bug.
The reason a separate maximum is needed at all is that the best path need not touch the root. A tree with a heavy subtree hanging off one side can have its diameter entirely inside that subtree, which is why returning the root's `left + right` alone is wrong.
Counting edges rather than nodes is the other trap: a leaf has height 1 in node terms but contributes 0 edges, so a single-node tree has diameter 0, not 1.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.