Pattern Recognition Drill

#139

Easy Trees

The Problem

Find the diameter (longest path between any two nodes) of a binary tree.

What approach would you use?

Think about it before scrolling down.

Diameter of Binary Tree

'Longest path' → diameter passes through some node as left_height + right_height
'Binary tree diameter' → post-order traversal tracking height, updating global max

Tree Recursion

Post-order: return height. At each node, update diameter = max(diameter, left_h + right_h). O(n).

Alt: DFS / Recursion

Same approach. The diameter is a side effect of computing heights.

Common Trap

Diameter is NOT always through the root. It can be entirely in a subtree.

← #138 #140 →