Compute binary tree diameter
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given the root of a binary tree, compute the tree's diameter defined as the maximum number of edges on any path between two nodes. Return the diameter, explain whether paths must pass through the root, and provide a solution with time and space complexity analysis. Handle empty and single-node trees.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute binary tree diameter states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given the root of a binary tree, compute the tree's **diameter**, defined as the maximum number of edges on any path between two nodes in the tree.
The path may or may not pass through the root: the longest path between two nodes might lie entirely within one subtree. For each node, the longest path that bends at that node has length `leftDepth + rightDepth` (in edges), where `leftDepth`/`rightDepth` are the heights of its left/right subtrees in edges. The diameter is the maximum of this quantity over all nodes.
The tree is provided as a level-order (breadth-first) array `values`, LeetCode style: index 0 is the root, and missing children are represented by `null` (`None` in Python). Rebuild the tree from this array, then compute and return the diameter as an integer.
Handle the empty tree (return 0) and the single-node tree (return 0, since a lone node has no edges).
Constraints
- 0 <= number of nodes <= 10^4
- Node values fit in a 32-bit signed integer (values are not used in the diameter computation).
- Input is a valid level-order serialization: index 0 is the root, missing children are null/None.
- The diameter is measured in EDGES, not nodes (an empty or single-node tree has diameter 0).
Examples
Input: ([1, 2, 3, 4, 5],)
Expected Output: 3
Explanation: Tree: 1->(2,3), 2->(4,5). Longest path 4-2-5 or 4-2-1-3: the path 4-2-1-3 has 3 edges, which is the diameter.
Input: ([],)
Expected Output: 0
Explanation: Empty tree: no nodes, so no edges and diameter 0.
Hints
- Diameter through a given node = (height of its left subtree) + (height of its right subtree), counted in edges. Take the max of this over all nodes.
- A single post-order DFS that returns each subtree's height while updating a running maximum solves it in O(n) — you do not need a separate height call per node (which would be O(n^2)).
- Don't assume the longest path passes through the root: it can live entirely inside one subtree. Track the global best in a mutable holder (or a return-by-reference) rather than only looking at the root.