Trees

Choose a tree traversal by when the information you need becomes available. A parent can pass constraints downward, a child can return a subtree summary upward, and a separate result can collect candidates discovered anywhere.

1. Decide What Flows Down and What Returns Up

Define empty-child results and units first. For node-count height, height(None)=0 and a leaf has height 1. An edge-count diameter uses a different unit. If both a subtree sum and its best internal answer are needed, return a tuple; rescanning each subtree can turn a linear traversal into quadratic work.

2. Combine Two Descending Chains at One Node

Every simple path in a tree has one node closest to the root. Splitting the path there gives at most one descending chain into each child subtree. This is the reference chapter's reusable idea for path problems.

For a binary tree's diameter in edges, return the best downward height, but update the overall diameter using both children:

def diameter(root):
    best = 0

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

    height(root)
    return best

left+right counts the edges on the best path passing through this node. Returning both branches upward would create a fork rather than a path; only one chain can be extended by the parent. Each node does constant combining work: $O(n)$ time and $O(h)$ stack space for height h.

For maximum path sum, use child gains max(0, child_gain) to drop harmful branches, update node.val+left_gain+right_gain, and return node.val+max(left_gain,right_gain). If a nonempty path is required, initialize the overall answer to -inf, not zero: an all-negative tree must select a real node. Aligned Path applies the same information-flow idea with its own allowed-node rule.

3. Use BST Ordering as a Global Constraint

Checking only left.val < node.val < right.val is insufficient. In a tree rooted at 10, a 12 anywhere in the left subtree violates the BST rule even if its own parent comparison passes.

Validate BST passes an open interval (low, high) downward. At node, require low < node.val < high; the left child inherits (low,node.val), the right (node.val,high). This enforces all ancestor constraints in $O(n)$ time and $O(h)$ space. Adjust inequalities only if the specified duplicate policy allows it.

An inorder traversal of a BST produces sorted values. For the kth smallest, stop after k visits; an explicit stack gives $O(h+k)$ time and $O(h)$ space. Two such iterators can merge BSTs in $O(n+m)$ time and $O(h_1+h_2)$ auxiliary space, excluding output. Searching for the closest value follows only the child on the target's side, updating the best candidate on the way: $O(h)$ time.

4. Levels, Ancestors, and Shape-dependent Costs

For BFS, enqueue the root only if it exists. At the start of a level, save level_size = len(queue) and process exactly that many nodes; children added during the loop belong to the next level. Alternatively, the chapter's node-depth queue stores (node,depth) pairs. Both use $O(n)$ time and $O(w)$ queue space, where w is maximum width. In Most Prolific Level, compare the next level's count with the current level's count; do not confuse the ratio with raw width.

For a lowest common ancestor with parent pointers, align the two depths and climb together until node identities match, or use an ancestor set. Without parent pointers, a postorder search can report whether targets were found below; if both sides report one, the current node is their split point. If target existence is not guaranteed, carry found flags/counts so a single found target is not mistaken for the LCA of both.

Use n for total work and h for path length. A balanced tree has $h=O(\log n)$; a skewed tree can have $h=O(n)$ and overflow a recursive stack. BFS may require $O(n)$ space on a wide tree even when its height is logarithmic. A perfect tree with h node levels has $2^h-1$ nodes; a complete tree fills the last level left to right. Neither property should be assumed for an arbitrary binary tree.

5. Key Takeaways

• Return one extendable chain to the parent, but consider both child chains when updating a complete path answer.
• Validate a BST against inherited bounds, not just immediate children.
• Save the queue size before processing a BFS level; newly enqueued children are the next level.
• Full traversal costs $O(n)$; recursive space is $O(h)$ and BFS space $O(w)$. Name the relevant shape before claiming logarithmic memory.

Review Recursion for multi-value return contracts. Continue to Graphs when nodes may have cycles or multiple incoming links, and Heaps for complete-tree ordering with a different invariant from a BST.