Neural Mastery
← Practice
Diameter of Binary Treemedium

Diameter of Binary Tree

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Graph & Tree Traversal, Step by Step
Structure
Algorithm
ABCDE
visiting A -> visited order so far: [A]
queue now: [B, C]
Step 1 / 5
Both modes run the real algorithm from the linked practice problem, one step at a time -- edit the graph or pick different tree nodes and every step recomputes live.

Implement Diameter of Binary Tree -- the classic "compute a global answer while also computing a per-node height" problem, solved in one pass by updating a running best as a side effect of the height recursion.

Related Skills

Task

Implement diameter_of_binary_tree(root): while computing each node's height (for the return value), also update a running "best diameter seen so far" using that node's left-height + right-height (the longest path THROUGH this node).

Function Signature

diameter_of_binary_tree(root: dict | None) -> int

Examples

Example 1: Classic 5-Node Tree
Input: root = {'val': 1, 'left': {'val': 2, 'left': {'val': 4, 'left': None, 'right': None}, 'right': {'val': 5, 'left': None, 'right': None}}, 'right': {'val': 3, 'left': None, 'right': None}}
Output: 3
Explanation: Longest path 4-2-1-3 or 5-2-1-3, 3 edges
Example 2: Two-Node Tree
Input: root = {'val': 1, 'left': {'val': 2, 'left': None, 'right': None}, 'right': None}
Output: 1

Constraints

  • Libraries are allowed; a plain-Python solution earns 10 bonus points.
  • The diameter is measured in EDGES, not nodes -- a 2-node tree has diameter 1, not 2.
  • The longest path does not need to pass through the root -- it could be entirely within one subtree.
  • Must run in O(n) time (a naive "recompute height from scratch at every node" approach is O(n^2)).
Python3Saved ✓
def diameter_of_binary_tree(root: dict | None) -> int:
"""root: a tree node as {'val', 'left', 'right'}, or None. Return
the length (number of EDGES, not nodes) of the longest path between
any two nodes in the tree -- this path may or may not pass through
the root."""
# Your implementation here
pass

Case 1: Classic 5-Node Tree
Input: root = {'val': 1, 'left': {'val': 2, 'left': {'val': 4, 'left': None, 'right': None}, 'right': {'val': 5, 'left': None, 'right': None}}, 'right': {'val': 3, 'left': None, 'right': None}}
Expected: 3
Case 2: Two-Node Tree
Input: root = {'val': 1, 'left': {'val': 2, 'left': None, 'right': None}, 'right': None}
Expected: 1