Preorder tree recursion

When to use it

Use it when a node needs something from the nodes above it, such as its level or a total so far, or must be handled before its children.

It belongs to the trees group: Let the shape of the data do the work: the branches of a tree, the letters of a trie, the top of a heap.

Watch it work

In a cave game every room holds coins and has up to two doors down to more rooms. You start at the top and take the coins of each room you enter. Return the coins you hold in each room with no door down, from left to right.

Input
root = [4, 2, 6, 3, 1, null, 5]

Output
[9, 7, 15]

root reaches the code as a tree, written here level by level: each node has a value, val, and two children, left and right.

The method

1. Keep a list for the answer: one total for each last room
2. A missing room: there is no door here, so do nothing
3. Work first: add this room's coins to the coins carried in
4. A room with no door down is a last room: record the total
5. Then call visit on each child, passing the new total down
6. Start in the top room carrying 0 coins, then return the list

The run, one moment at a time

1. Step 1. No room has been entered. The list of totals is empty.

   from above: empty
   now holds: empty
   totals: empty
   

2. Step 6. solve calls visit on the top room, 4, with 0 coins. From here on visit calls itself.

   from above: 0
   now holds: empty
   totals: empty
   

3. Step 3. Room 4 gets 0 from above. It does its own work first, before any child is called: 0 + 4 = 4.

   from above: 0
   now holds: 4
   totals: empty
   

4. Step 5. Room 4 has doors down. It calls visit on its left child, room 2, and passes 4 down. The right child will get the same 4 later.

   from above: 0
   now holds: 4
   totals: empty
   

5. Step 3. Room 2 gets 4 from room 4 and adds its own coins on the way down: 4 + 2 = 6.

   from above: 4
   now holds: 6
   totals: empty
   

6. Step 3. Room 3 gets 6 from room 2 and adds its own coins on the way down: 6 + 3 = 9.

   from above: 6
   now holds: 9
   totals: empty
   

7. Step 4. Room 3 has no door down, so it is a last room. Its total, 9, goes into the list.

   from above: 6
   now holds: 9
   totals: 9
   

8. Step 2. Room 3 still calls visit on its two missing children. Each call finds no room and returns at once, so the walk turns back here.

   from above: 6
   now holds: 9
   totals: 9
   

9. Step 4. Back in room 2 the coins are still 6: room 3 added its 3 inside its own call. Room 1 gets 6: 6 + 1 = 7. No door down, so 7 goes into the list.

   from above: 6
   now holds: 7
   totals: 9 7
   

10. Step 3. Back at room 4, the coins are still 4, so its right child, room 6, also gets 4: 4 + 6 = 10.

    from above: 4
    now holds: 10
    totals: 9 7
    

11. Step 4. Room 5 gets 10 from room 6: 10 + 5 = 15. It has no door down, so 15 goes into the list.

    from above: 10
    now holds: 15
    totals: 9 7 15
    

12. Step 6. Every room was entered once, each parent before its children. The 3 last rooms recorded 9, 7, 15: that list is the answer.

    from above: empty
    now holds: empty
    totals: 9 7 15
    

The code

The numbered comments are the steps of the method.

function solve(root) {
  // 1. Keep a list for the answer: one total for each last room
  const totals = [];
  function visit(room, coins) {
    // 2. A missing room: there is no door here, so do nothing
    if (!room) return;
    // 3. Work first: add this room's coins to the coins carried in
    coins += room.val;
    // 4. A room with no door down is a last room: record the total
    if (!room.left && !room.right) totals.push(coins);
    // 5. Then call visit on each child, passing the new total down
    // visit calls itself: the same job, one room lower.
    visit(room.left, coins);
    visit(room.right, coins);
  }
  // 6. Start in the top room carrying 0 coins, then return the list
  visit(root, 0);
  return totals;
}

def solve(root):
    # 1. Keep a list for the answer: one total for each last room
    totals = []

    def visit(room, coins):
        # 2. A missing room: there is no door here, so do nothing
        if room is None:
            return
        # 3. Work first: add this room's coins to the coins carried in
        coins += room.val
        # 4. A room with no door down is a last room: record the total
        if room.left is None and room.right is None:
            totals.append(coins)
        # 5. Then call visit on each child, passing the new total down
        # visit calls itself: the same job, one room lower.
        visit(room.left, coins)
        visit(room.right, coins)

    # 6. Start in the top room carrying 0 coins, then return the list
    visit(root, 0)
    return totals

How to spot it

Given: The path to a node: the nodes from the root down to it

The root is the top node. A problem that defines this path usually has a rule about it, and each parent hands down a summary of the path so far.

Asked: Each node needs its level, counted from the root

A node cannot see above itself. Its parent knows its own level and passes that number plus one to each child.

Asked: Write the tree out, each node before its children

The node is handled first and its two sides after it, each side in the same way. That order is preorder.

Looks like it, but is not

• A node's answer needs a result from below it, such as its height or the total of everything under it. Use Postorder tree recursion. That result exists only after the children have finished. The node must wait and do its work on the way back up.
• The answer lists the nodes one level at a time, from left to right. Use Level-order tree traversal. This walk finishes the whole left side before it starts the right, so the nodes of one level are met far apart.
• You go down from the root and at each node choose one side by comparing values. Use Binary search tree ordering. That follows one path and never comes back for the other side, so no function has to call itself on both children.

Cost and mistakes

Time grows with the number of nodes, written O(n): each node is entered once. Extra space is one waiting call for each level of the tree, written O(h) for a tree of height h. Each call carries its own copy of the value passed down.

Watch out

• Pass the value down as an argument, not in one shared variable. When the walk comes back up and goes down into the other child, a shared variable still holds what the first side added.
• Do the node's own work before the two calls. If it comes after them, the children have already run with a value that does not include their parent.

In the 150

5 problems of the 150 use it. Naming them gives their method away, so the list is folded.