Postorder tree recursion

When to use it

Use it when a node's answer is built from the answers of its children, so the children must finish first: that order is what postorder means.

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

Each shop of a company made a profit or a loss and has up to two shops below it. A shop's result is its own number plus the results of those two shops. A result under 0 counts as 0: the branch is closed. Return the top shop's result.

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

Output
12

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. A missing shop has no result: hand back 0
2. Ask the left child, then the right child, and wait for both
3. Both have answered: add this shop's own number to their results
4. Hand the total up to the parent, or 0 if it is under 0

The run, one moment at a time

1. Step 2. Start at the top, shop 3. It cannot answer yet: it calls solve on its left child, shop -6, and waits for the result.

   waiting: empty
   gave back: ? ?  (left at 0, right at 1)
   total: empty
   hands up: empty
   

2. Step 2. Shop -6 cannot answer yet either. It calls solve on its own left child, shop 1, and waits. Now shop 3 waits for shop -6.

   waiting: 3
   gave back: ? ?  (left at 0, right at 1)
   total: empty
   hands up: empty
   

3. Step 1. Shop 1 asks its children too, but it has none. Each missing child hands back 0 at once. Here the asking stops and the answers start.

   waiting: 3 -6
   gave back: 0 0  (left at 0, right at 1)
   total: empty
   hands up: empty
   

4. Step 4. Shop 1 adds its own number: 1 + 0 + 0 = 1. That is not under 0, so it hands 1 up to shop -6.

   waiting: 3 -6
   gave back: 0 0  (left at 0, right at 1)
   total: 1
   hands up: 1
   

5. Step 4. Shop -6 has asked shop 4, which has no children either: 4 + 0 + 0 = 4. Shop 4 hands 4 up to shop -6.

   waiting: 3 -6
   gave back: 0 0  (left at 0, right at 1)
   total: 4
   hands up: 4
   

6. Step 3. Both children of shop -6 have answered. Only now does it do its own work: -6 + 1 + 4 = -1.

   waiting: 3
   gave back: 1 4  (left at 0, right at 1)
   total: -1
   hands up: empty
   

7. Step 4. The total, -1, is under 0, so this branch is closed. Shop -6 hands 0 up to shop 3.

   waiting: 3
   gave back: 1 4  (left at 0, right at 1)
   total: -1
   hands up: 0
   

8. Step 2. The left side has answered 0. Shop 3 still cannot finish: it calls solve on its right child, shop 2, and waits again.

   waiting: empty
   gave back: 0 ?  (left at 0, right at 1)
   total: empty
   hands up: empty
   

9. Step 4. Shop 2 has asked shop 7, which has no children either: 7 + 0 + 0 = 7. Shop 7 hands 7 up to shop 2.

   waiting: 3 2
   gave back: 0 0  (left at 0, right at 1)
   total: 7
   hands up: 7
   

10. Step 4. For shop 2, the missing left child counts as 0 and shop 7 handed back 7: 2 + 0 + 7 = 9. It hands 9 up to shop 3.

    waiting: 3
    gave back: 0 7  (left at 0, right at 1)
    total: 9
    hands up: 9
    

11. Step 3. Both children of shop 3 have answered, 0 and 9. The top shop works last: 3 + 0 + 9 = 12.

    waiting: empty
    gave back: 0 9  (left at 0, right at 1)
    total: 12
    hands up: empty
    

12. Step 4. The total, 12, is not under 0, and there is no parent to hand it to. The result of the top shop is 12.

    waiting: empty
    gave back: 0 9  (left at 0, right at 1)
    total: 12
    hands up: 12
    

The code

The numbered comments are the steps of the method.

function solve(root) {
  // 1. A missing shop has no result: hand back 0
  if (!root) return 0;
  // 2. Ask the left child, then the right child, and wait for both
  // solve calls itself: the same job, for the smaller tree below.
  const left = solve(root.left);
  const right = solve(root.right);
  // 3. Both have answered: add this shop's own number to their results
  const total = root.val + left + right;
  // 4. Hand the total up to the parent, or 0 if it is under 0
  return Math.max(total, 0);
}

def solve(root):
    # 1. A missing shop has no result: hand back 0
    if root is None:
        return 0
    # 2. Ask the left child, then the right child, and wait for both
    # solve calls itself: the same job, for the smaller tree below.
    left = solve(root.left)
    right = solve(root.right)
    # 3. Both have answered: add this shop's own number to their results
    total = root.val + left + right
    # 4. Hand the total up to the parent, or 0 if it is under 0
    return max(total, 0)

How to spot it

Asked: Return the height, the size or the total of a tree

For a node, each of these is made from its own part and the same number from each child. So the children must answer first.

Given: A path may join any two nodes, not only go down from the top

Such a path climbs to one highest node and goes down again. That node needs the best way down on each side, and its children hand those up.

Asked: A rule at every node about the height or total of its two sides

Each side's number is ready only after that side has finished. So the children report first, and the node tests the rule on the way back up.

Limits: Up to 100,000 nodes, so no height or total can be worked out twice

On a tree that is one long chain, working out the height again at every node costs about 5 billion steps. Handing it up costs one visit per node.

Looks like it, but is not

• What a node needs comes from above it, such as its level or a total collected on the way down. Use Preorder tree recursion. Only the parent knows what is above. It must pass that down before its children start, so the node works first.
• The answer is grouped by level, or asks for the node nearest to the top. Use Level-order tree traversal. This walk finishes one whole side before it starts the other, so it mixes the levels. Reading level by level keeps them apart.
• The tree is a binary search tree and you are looking for one value. Use Binary search tree ordering. A comparison tells you which child to go to, so one path down is enough. No answers have to be combined.

Cost and mistakes

Time grows with the number of nodes, written O(n): each node is visited once and does a fixed amount of work. Extra space is one waiting call for each level of the tree, written O(h) for a tree of height h.

Watch out

• Start the function with the answer for a missing node. That line is where the calls stop. Without it the code goes below a node with no children, reads the value of nothing, and fails.
• A node may hand one thing up and record another. When the question is about the best node anywhere, keep the best in a variable outside the function and still return what the parent needs.

In the 150

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