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 Amazon.

What role is this question designed for?

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

Compute tree diameter | Amazon Coding Question

Quick Overview

This question evaluates understanding of binary tree algorithms, recursion versus iterative traversal strategies, and competence in algorithmic analysis including time and space complexity and handling deep-recursion stack overflow when computing a tree's diameter.

Compute tree diameter

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a (potentially large) binary tree, compute its diameter (the number of edges on the longest path between any two nodes). Implement an O(n) solution, explain your recursion or iterative strategy, and justify correctness. Discuss how you would handle very deep trees to avoid stack overflow, and analyze time and space complexity.

Quick Answer: This question evaluates understanding of binary tree algorithms, recursion versus iterative traversal strategies, and competence in algorithmic analysis including time and space complexity and handling deep-recursion stack overflow when computing a tree's diameter.

Given a binary tree serialized in level-order (LeetCode style) as an array `tree`, return its **diameter**: the number of edges on the longest path between any two nodes. The path does not need to pass through the root. The input array lists node values level by level, using `null`/`None` for an absent child. Only the children of present nodes appear in the array. For example `[1, 2, 3, 4, 5]` is: ``` 1 / \ 2 3 / \ 4 5 ``` Its diameter is 3 (e.g. 4 → 2 → 1 → 3). Implement an O(n) solution. Because the tree may be very deep, prefer a strategy that avoids stack overflow (an explicit stack / iterative post-order, or an explicitly bounded recursion). For each subtree compute its height in nodes; the longest path that bends at a given node uses `leftHeight + rightHeight` edges, and the answer is the maximum over all nodes.

Constraints

0 <= number of nodes <= 10^5
The tree may be highly unbalanced (effectively a linked list of depth up to n), so a naive recursive solution can overflow the call stack.
Node values fit in a 32-bit signed integer and do not affect the diameter.
An empty tree or a single node has diameter 0.

Examples

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

Expected Output: 3

Explanation: Tree is 1 with children 2,3 and 2 with children 4,5. Longest path 4-2-1-3 has 3 edges; it bends at node 1 but does not extend to a deeper leaf, so the diameter is 3.

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

Expected Output: 4

Explanation: A left-skewed chain 1-2-3-4-5 (each node has only a left child). The longest path runs end to end with 4 edges, exercising the deep-tree case.

Input: ([1],)

Expected Output: 0

Explanation: A single node has no edges, so the diameter is 0.

Input: ([],)

Expected Output: 0

Explanation: An empty tree has diameter 0.

Input: ([1, 2, 3],)

Expected Output: 2

Explanation: Perfectly balanced 3-node tree. Path 2-1-3 has 2 edges.

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

Expected Output: 2

Explanation: A right-skewed chain 1-2-3 has 2 edges, the mirror of the left-skewed case.

Hints

The diameter at a node equals leftHeight + rightHeight (counting edges). Track a running maximum of this quantity while you also return each subtree's height.
Heights are needed bottom-up, so compute them in a post-order traversal: a node can only be finalized after both its children are done.
To survive very deep trees, replace recursion with an explicit stack (push each node twice — once to descend, once to process) so the OS call stack is never the bottleneck.

Quick Overview