Trees · 071Easy
Diameter of Binary Tree
Given the root of a binary tree, return its diameter: the length of the longest path between any two nodes, measured in EDGES. The path need not pass through the root.
Constraints
- The tree holds 1 to 10^4 nodes.
- -100 <= Node.val <= 100
- INPUT FORMAT
- `root` is a TreeNode object, not an array. The arrays in EXAMPLES are the level-order
- serialization the platforms print — breadth-first, with `null` for a missing child. The
- test runner builds a real tree from that array before calling your function.
Examples
diameterOfBinaryTree([1, 2, 3, 4, 5]) -> 3 // path 4 - 2 - 1 - 3 diameterOfBinaryTree([1, 2]) -> 1 diameterOfBinaryTree([1]) -> 0 // a single node has no edges diameterOfBinaryTree([1, 2, 3, 4, 5, 6, 7]) -> 4 // perfectly balanced: 4 - 2 - 1 - 3 - 6 diameterOfBinaryTree([1, null, 2, null, 3]) -> 2 // a skewed chain of three nodes diameterOfBinaryTree([1, 2, null, 3, null, 4]) -> 3 // left-skewed chain of four
Edge cases
- A single node has diameter 0, not 1.
- Edges, not nodes: a path of k nodes has k - 1 edges.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — compute both subtree heights afresh at every node.
- Target
- O(n) time, O(h) space — one DFS returning height while updating a running best of (leftHeight + rightHeight) at each node.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/07-trees/071-diameter-of-binary-tree.js ./practice c 071