How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Compute binary tree diameter | Meta Coding Question

Quick Overview

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.

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.

Input: ([1],)

Expected Output: 0

Explanation: Single node: a lone node has no edges, so the diameter is 0.

Input: ([1, 2],)

Expected Output: 1

Explanation: Two nodes 1->2: the only path has a single edge, diameter 1.

Input: ([1, 2, None, 3, None, 4, None, 5],)

Expected Output: 4

Explanation: Degenerate left-leaning chain 1->2->3->4->5. The longest path runs the full chain: 4 edges.

Input: ([1, 2, 3, 4, 5, None, None, 6, 7, None, None, 8, 9],)

Expected Output: 5

Explanation: Level-order build yields 1->(2,3); 2->(4,5); 4->(6,7); 6->(8,9). The diameter path 8-6-4-2-1-3 has 5 edges and passes through the root, while the path entirely within node 2's subtree is shorter — a case showing the max must be taken over all nodes.

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.

Quick Overview