Module 17 · Binary Trees: Recursive DFS and Structural Contracts

168. Diameter of Binary Tree

Interview · Download this solution · All solutions and shared helpers

Problem

Return the diameter of a binary tree: the largest number of edges on any simple path between two nodes. The path need not pass through the root. Return zero for an empty tree or a singleton. Leave the tree unchanged.

Examples

Example 1

tree_diameter(build_tree([1,2,3,4,5]))
=> 3

The path 4-2-1-3 has three edges.

Example 2

tree_diameter(None)
=> 0

There is no nonzero path.

Example 3

tree_diameter(build_tree([1,2,None,3,None,4]))
=> 3

A four-node chain has three edges.

Reveal the worked solution and reasoning

Why this mechanism works

A downward path can choose only one child, while a complete path through a node can join two child arms. Therefore each call returns height to its parent and separately updates the best diameter. Using node-count child heights makes left_height+right_height equal the number of edges on the joined path.

State and boundaries

height(node) returns node-count height. best stores the maximum through-node edge count among nodes already summarized.

Protocol

Return height zero for None.
Obtain both child heights.
Update best with their sum.
Return one plus their maximum.
Return best after the root summary.

Visualization

left height 2 -- current node -- right height 3
through-node path = 2+3 = 5 edges
upward height = 1+max(2,3) = 4 nodes

Python implementation

from structures import build_tree

def tree_diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)
    height(root)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

tree_diameter(build_tree([1,2,3,4,5]))

L4 tree_diameter: best = 0
root=N1(val=1,left=N2,right=N3); best=0

L7 height: if node is None:
node=N1(val=1,left=N2,right=N3); best=0

L7 height: if node is None:
node=N2(val=2,left=N4,right=N5); best=0

L7 height: if node is None:
node=N4(val=4,left=None,right=None); best=0

L7 height: if node is None:
node=None; best=0

L7 height: if node is None:
node=None; best=0

L9 height: left, right = height(node.left), height(node.right)
node=N4(val=4,left=None,right=None); best=0; left=0; right=0

L7 height: if node is None:
node=N5(val=5,left=None,right=None); best=0

... 8 intermediate state changes omitted ...

L9 height: left, right = height(node.left), height(node.right)
node=N3(val=3,left=None,right=None); best=2; left=0; right=0

L9 height: left, right = height(node.left), height(node.right)
node=N1(val=1,left=N2,right=N3); best=2; left=2; right=1

L10 height: best = max(best, left + right)
node=N1(val=1,left=N2,right=N3); best=3; left=2; right=1

L12 tree_diameter: height(root)
root=N1(val=1,left=N2,right=N3); best=3

Result: 3. The path 4-2-1-3 has three edges.

tree_diameter(None)

L4 tree_diameter: best = 0
root=None; best=0

L7 height: if node is None:
node=None; best=0

Result: 0. There is no nonzero path.

Why the solution is correct

Every simple path has a highest node, where it splits into at most one arm in each child subtree. The child heights give the longest possible arms through that node. Taking the maximum of these candidates over all nodes considers an optimum path, while no candidate exceeds a valid path length.

Time and space

O(n) time and O(h) recursive stack space. Each subtree height is computed once.

Common mistakes

Returning left+right to the parent offers a forked path that cannot be extended as one arm. Recomputing heights separately at every node can take quadratic time.

Reasoning card

State: height(node) returns node-count height. best stores the maximum through-node edge count among nodes already summarized.

Invariant: Height and best diameter have distinct meanings.

Decision to rehearse: Each call returns height while updating a global/nonlocal through-node path.

Finish: Return best after the root summary

Transfer exercise

Return the actual diameter endpoints along with height and deepest descendant information.