Skip to content

Preorder Template

Platform Connection — Parameter Fixing: When you pass remainingSum = 22 from the root and subtract each node's value as you descend, you're doing exactly what our DP course calls parameter fixing. At the root, the problem is unconstrained. At the left child (value 5), the parameter tightens: "your entire subtree must find a path summing to 17." Each level fixes one more dimension of the problem until a leaf either satisfies or violates the constraint.

Information Flows Two Ways

In every problem so far, information flowed up. Leaves computed something, parents combined it. The root got the final answer. That's bottom-up — postorder.

But some questions can't be answered bottom-up. Consider: "Does any root-to-leaf path sum to 22?" A leaf doesn't know what's above it. It sees its own value — say, 2 — and has no idea whether the nodes above sum to 20.

The information the leaf needs lives at the root. It has to be passed down.

Top-down (preorder) pattern: carry accumulated state as a parameter. Process the node BEFORE recursing into children. The state grows as you descend.

This is the opposite direction from postorder. In postorder, you wait for children to report back. In preorder, you tell children what they need to know.

The Template

Every top-down problem follows this shape:

void preorder(TreeNode* node, State accumulated) {
    if (!node) return;
    State updated = combine(accumulated, node->val);
    if (!node->left && !node->right) {
        process(updated);
        return;
    }
    preorder(node->left, updated);
    preorder(node->right, updated);
}

Three moving parts:

  1. accumulated — what you've gathered so far from root to here.
  2. combine — how this node's value extends the accumulated state.
  3. process — what to do at a leaf (or along the way).

The leaf check (!left && !right) matters. If you don't check it, you'll process nullptr children as if they were leaves and double-count paths.

Top-down preorder: accumulated state flows from root to leaves, growing at each node

Problem 1: Root-to-Leaf Sum (LC 112)

Problem: Given a binary tree and an integer targetSum, return true if there exists a root-to-leaf path where the values sum to targetSum.

        5
       / \
      4   8
     /
    11
   /  \
  7    2

Target sum = 22. The path 5 → 4 → 11 → 2 sums to 22. Answer: true.

The accumulated state is the running sum from root to the current node. At each node, you add the node's value. At a leaf, you check if the sum equals the target.

Full Trace

Starting with runningSum = 0 at the root:

Node Running Sum Before After Adding Node Is Leaf? Check
5 0 5 No —
4 5 9 No —
11 9 20 No —
7 20 27 Yes \(27 \neq 22\)
2 20 22 Yes \(22 = 22\) — found!

The recursion short-circuits when it finds a match. We never even visit node 8.

The Code

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    int remaining = targetSum - root->val;
    if (!root->left && !root->right) return remaining == 0;
    return hasPathSum(root->left, remaining) || hasPathSum(root->right, remaining);
}

Notice: instead of accumulating the sum upward, we subtract the node's value from the target. When we reach a leaf, we check if the remaining target is 0. Same logic, slightly cleaner — no extra parameter needed because targetSum itself carries the state.

Complexity: \(O(n)\) time, \(O(h)\) space where \(h\) is the tree height (recursion stack).

Problem 2: Root-to-Leaf Paths as Strings (LC 257)

Problem: Return all root-to-leaf paths as strings in the format "1->2->5".

Same tree:

        5
       / \
      4   8
     /
    11
   /  \
  7    2

Expected output: ["5->4->11->7", "5->4->11->2", "5->8"]

Here the accumulated state is a string — the path built so far. At each node, append the node's value. At a leaf, save the completed path.

Full Trace

Node Path So Far After Appending Is Leaf? Action
5 "" "5" No recurse
4 "5" "5->4" No recurse
11 "5->4" "5->4->11" No recurse
7 "5->4->11" "5->4->11->7" Yes save path
2 "5->4->11" "5->4->11->2" Yes save path
8 "5" "5->8" Yes save path

Key observation: when we backtrack from 7 to 11, the path is still "5->4->11". The string "5->4->11->7" was a local copy — it doesn't pollute the path for 2. This is why passing state by value (not by reference) gives you automatic backtracking for free.

The Code

void allPaths(TreeNode* node, string pathSoFar, vector<string>& result) {
    if (!node) return;
    string currentPath = pathSoFar.empty()
        ? to_string(node->val)
        : pathSoFar + "->" + to_string(node->val);
    if (!node->left && !node->right) {
        result.push_back(currentPath);
        return;
    }
    allPaths(node->left, currentPath, result);
    allPaths(node->right, currentPath, result);
}

vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> result;
    allPaths(root, "", result);
    return result;
}

Complexity: \(O(n \cdot h)\) time (each path is up to \(h\) long, and string concatenation costs \(O(h)\)), \(O(n \cdot h)\) space for storing all paths.

Bottom-Up vs Top-Down: When to Use Which

The distinction is simple:

  • Bottom-up (postorder): the answer at a node depends on answers from its children. Example: height, diameter, subtree sum.
  • Top-down (preorder): the answer at a node depends on information from its ancestors. Example: root-to-leaf sum, depth, path string.

Some problems can be solved either way. Root-to-leaf sum can be done top-down (accumulate sum going down) or bottom-up (subtract from target). But the top-down framing is more natural when the question involves "the path from root to here."

Rule of thumb: if the problem says "root-to-leaf" or "root-to-node," think top-down. If it says "subtree" or "combine children," think bottom-up.

Try It

The starter code has a hasPathSum function with a TODO. Fill in the body.

Input: Tree = [5,4,8,11,null,null,null,7,2], targetSum = 22
Output: true

Predict before running: What does hasPathSum return on a single-node tree with val = 5 and targetSum = 5? Trace it: remaining = 5 - 5 = 0, node is a leaf, return 0 == 0 → true. Correct.

Challenge: What if targetSum = 0 and the tree is a single node with val = 0? What if the tree has val = 0 but also has children? Make sure your solution handles both.

Edge Cases to Watch For

  • Node with only one child: If root->left is null but root->right is not, node root is NOT a leaf. Do not check for a path sum match at root. You must guard with !root->left && !root->right before declaring a leaf match, otherwise the path incorrectly terminates at an internal node.

Problems

Problem Link Difficulty
LC 112 — Path Sum leetcode.com/problems/path-sum Easy
LC 257 — Binary Tree Paths leetcode.com/problems/binary-tree-paths Easy
LC 113 — Path Sum II leetcode.com/problems/path-sum-ii Medium
LC 129 — Sum Root to Leaf Numbers leetcode.com/problems/sum-root-to-leaf-numbers Medium