Chapter 5 · Trees and heaps

A tree problem becomes easier when the recursive function has a one-sentence contract.

Thinking flow · What information must move?

flowchart TD
  accTitle: Choosing a tree traversal, recursive state, or heap
  accDescr: Use preorder when parent state must reach children, postorder when children must be combined into a parent answer, inorder for sorted binary-search-tree order, and level-order BFS for minimum edge depth or layer processing. Use a heap instead of a tree traversal when the problem is a changing candidate set whose next minimum or maximum is repeatedly requested.
  A{"Is the input a hierarchy<br/>or a changing candidate set?"}
  A -->|"tree / hierarchy"| B{"Where does required<br/>information come from?"}
  B -->|"parent before children"| C["Preorder DFS<br/>carry path state down"]
  B -->|"children before parent"| D["Postorder DFS<br/>return subtree summary"]
  B -->|"sorted BST order"| E["Inorder traversal<br/>plus BST bounds"]
  B -->|"level / minimum edge depth"| F["Level-order BFS"]
  A -->|"changing candidates"| G{"Need the next minimum<br/>or maximum repeatedly?"}
  G -->|yes| H["Heap / priority queue"]
  G -->|no| I["Sort once or use<br/>a direct scan"]

Choose the dependency direction before choosing recursive or iterative syntax. Both mechanisms can implement preorder or postorder; the contract determines which order is correct.

dfs(node) returns the height of the complete subtree rooted at node.

flowchart TD
  accTitle: Recursive dependencies for tree height
  accDescr: Height of a node depends on the independently computed heights of its left and right subtrees, followed by one plus their maximum; an empty subtree returns zero.
  R["height(node)"] --> L["height(node.left)"]
  R --> Q["height(node.right)"]
  L --> B["empty → 0<br/>node → recurse"]
  Q --> C["empty → 0<br/>node → recurse"]
  B --> M["return 1 + max(left, right)"]
  C --> M

From that contract:

1. the empty subtree returns zero;
2. recursively obtain left and right heights;
3. return one plus their maximum.

PythonC++17C++11

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class TreeNode:
    """A minimal binary-tree node used by the reference examples."""

    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def tree_height(root: TreeNode | None) -> int:
    """Return the number of nodes on the longest root-to-leaf path."""
    # An empty subtree contributes no nodes.
    if root is None:
        return 0
    # Solve both child contracts before combining their answers.
    left_height = tree_height(root.left)
    right_height = tree_height(root.right)
    return 1 + max(left_height, right_height)

struct TreeNode {
  explicit TreeNode(int node_value, TreeNode* left_child = nullptr,
                    TreeNode* right_child = nullptr)
      : value(node_value), left(left_child), right(right_child) {}

  int value;
  TreeNode* left;
  TreeNode* right;
};

inline int tree_height(const TreeNode* root) {
  // An empty subtree contributes no nodes.
  if (root == nullptr) {
    return 0;
  }
  // Solve both child contracts before combining their answers.
  const int left_height = tree_height(root->left);
  const int right_height = tree_height(root->right);
  return 1 + std::max(left_height, right_height);
}

struct TreeNode {
  explicit TreeNode(int node_value, TreeNode* left_child = nullptr,
                    TreeNode* right_child = nullptr)
      : value(node_value), left(left_child), right(right_child) {}

  int value;
  TreeNode* left;
  TreeNode* right;
};

inline int tree_height(const TreeNode* root) {
  // An empty subtree contributes no nodes.
  if (root == nullptr) {
    return 0;
  }
  // Solve both child contracts before combining their answers.
  const int left_height = tree_height(root->left);
  const int right_height = tree_height(root->right);
  return 1 + std::max(left_height, right_height);
}

The base case and return statement are direct translations of the contract. For a chain of three nodes the calls return 1, then 2, then 3; for an empty root they return 0.

Traversal order follows dependency

Need	Order
consume parent before children	preorder
sorted order in a BST	inorder
aggregate children into parent	postorder
minimum edge count from root	level-order BFS

Do not choose recursive vs iterative first. Choose the information dependency, then select a mechanism.

Recursive safety

Recursive DFS uses O(h) call-stack space. A balanced tree has h = O(log n); a chain has h = O(n). Python can reach its recursion limit, and C++ can exhaust the process stack. Use an explicit stack when depth is not bounded.

Binary search tree invariant

For every node:

• every key in the left subtree is smaller;
• every key in the right subtree is larger;
• the duplicate policy is explicit.

Passing lower and upper bounds through recursion is safer than checking only the immediate children.

Heap mental model

A heap guarantees only that the root is extreme. It does not keep the complete container sorted. Use it when the repeated operation is “give me the next smallest/largest live candidate.”

For streaming medians, maintain:

• a max-heap for the lower half;
• a min-heap for the upper half;
• an ordering invariant between halves;
• a size difference of at most one.

When averaging two C++ int tops, convert before addition to avoid overflow. The tested implementation is in structures.py and its C++ counterpart in algorithms.hpp.

Practice ladder · define the subtree contract

Rung	Problem	Thinking prompt
1	Maximum Depth of Binary Tree	What does one call return for an empty subtree?
2	Binary Tree Level Order Traversal	How does the queue separate levels?
3	Validate Binary Search Tree	Which ancestor bounds reach this node?
4	Binary Tree Maximum Path Sum	What may extend upward, and what may finish here?

For heap practice, add Kth Largest Element in an Array and explain why sorting the whole input is unnecessary.