DSA FOUNDATION

Tree foundations: structure, depth, and traversal state

Choose the tree contract, traversal continuation, returned summary, and global objective separately.

Mechanism and state

A proper tree is finite and acyclic with one parent per nonroot identity; equal values do not identify objects. Compact level order consumes two child slots per queued nonnull parent and is not a heap-index formula. Preorder can perform local edge swaps, paired DFS compares exact same-side or mirror-side positions, inorder emits strict BST ranks, and BFS freezes one level before adding children. Postorder frames store a node, continuation stage, and two child results so deep trees do not depend on Java recursion.

Why the pattern works

Define what flows upward separately from what is optimized globally. Height returns 1+max(child heights). Diameter considers both child heights as an edge-count candidate at every node. Maximum path sum returns a one-arm downward gain, while its global nonempty candidate can use two optional nonnegative arms. Balance propagates a height only after certifying both children and the local gap. Global BST bounds retain every ancestor inequality. LCA membership is reference reachability, and a complete preorder grammar with # null markers uniquely determines ordered shape.

Work through an example

For [3,9,20,null,null,15,7], compact decoding gives root children 9 and 20, two absent children under 9, and 15/7 under 20. Depth is three nodes but diameter is three edges. In [-3,-2,-5], maximum nonempty path sum is -2, not an empty zero. For [5,1,7,null,null,4,8], 4 passes a parent-only test against 7 but violates the inherited lower bound 5. During postorder, stage 1 resumes after left and stage 2 resumes after right; a parent frame keeps returned child summaries.

Where the reasoning fails

A 100,000-node chain can overflow recursive Java calls even when the recurrence is linear. Live DFS continuations use O(h), BFS queue O(w), and output/history/token arrays must be counted separately. A stage-2 frame suspended below a child is not ready to combine until it becomes top again. Inversion mutates existing links; read-only queries must preserve every edge. Codec output uses fresh identities and strict full-message parsing. Null bounds in diagrams mean unbounded intervals, not unsafe JavaScript long numbers. Long path sums widen before addition.

Reconstruct the reasoning