Reference: LeetCode
Difficulty: Hard

Problem

Given a binary tree, return the postorder traversal of its nodes’ values.

Example: 

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Analysis

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> postorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  postorder(root, result);
  return result;
}

private void postorder(TreeNode root, List<Integer> result) {
  if (root == null) {
    return;
  }
  postorder(root.left, result);
  postorder(root.right, result);
  result.add(root.val);
}

Time: $O(N)$
Space: $O(h)$

Note: Another way to use recursion is related to functional programming.

1
2
3
4
5
6
7
8
9
10
11
12
// Assume we process a tree [4,1,#,3,2]
//     4
//    /
//   1 
//  / \
// 3   2
post([4,1,#,3,2]) = post(4)
= post([1]) + post([3,2]) + [4]
= [1] + post(3) + [4]
= [1] + post([2]) + [3] + [4]
= [1] + [2, 3] + [4]
= [1, 2, 3, 4]

Iteration (preorder-like)

Original postorder traversal is difficult to be simulated with stack. We can apply reversed-postorder traversal.

We can compare postorder and reversed-postorder traversals.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
     2
   /   \
  1     3
 /               postorder: 0 -> 1 -> 3 -> 2
0       reversed-postorder: 2 -> 3 -> 1 -> 0

// postorder
postorder(TreeNode root) {
  if (root == null) return;
  postorder(root.left)
  postorder(root.right)
  print(root.val)
}

// reversed-postorder
rev_postorder(TreeNode root) {
  if (root == null) return;              while (stack.size() > 0) {
  print(root.val);                         root = stack.pop();
  postorder(root.right);        ----->     if (root.left != null)  stack.push(root.left);
  postorder(root.left);                    if (root.right != null) stack.push(root.right);
}                                        }

// finally reverse the output
postorder(root) = reverse(rev_postorder(root));

In the reversed-postorder traversal, we can see that this form of code is exactly like the preorder traversal. So, we can use the iteration code in preorder traversal.

Iteration Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postorder(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  if (root == null) {
    return result;
  }
  stack.push(root);
  
  while (stack.size() > 0) {
    TreeNode curr = stack.pop();
    result.addFirst(curr.val); // addFirst() leads to a reversed result

    if (curr.left != null)  stack.push(curr.left);    // left goes first
    if (curr.right != null) stack.push(curr.right);
  }
  return result;
}

Time: $O(N)$
Space: $O(h)$

Iteration (inorder-like)

Like the inorder traversal, we go down to the left of the tree. But this time, we push a node p‘s right child to the stack if it is not null before pushing its left child. This actually means that in the future before visiting the node p, we would visit its right child first.

“while” version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<Integer> postorderTraversal(TreeNode root) {
  if (root == null) {
    return new ArrayList<>();
  }
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();

  TreeNode p = root; // no need to push into stack
  while (p != null || stack.size() > 0) {
    // go leftmost (this time we also push right child if it is not null)
    while (p != null) {
      if (p.right != null) stack.push(p.right); // push right child before p
      stack.push(p);
      p = p.left;
    } // p -> null

    p = stack.pop(); // pop

    // if p.right is at the top of stack, i.e. it is not yet processed
    if (stack.size() > 0 && p.right == stack.peek()) {
      stack.pop(); // pop its right from stack
      stack.push(p);  // push p to stack to process it in the future
      p = p.right; // next time process p.right
    }
    else { // p.right == null OR p.right is processed
      result.add(p.val);
      p = null; // next time, don't visit left child
    }
  }
  return result;
}

“if” version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<Integer> postorderTraversal(TreeNode root) {
  if (root == null) {
    return new ArrayList<>();
  }
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();

  TreeNode p = root;
  while (p != null || stack.size() > 0) {
    if (p != null) {
      if (p.right != null) stack.push(p.right);
      stack.push(p);
      p = p.left;
    }
    else { // p == null
      p = stack.pop();
      if (stack.size() > 0 && p.right == stack.peek()) {
        // visit right child
        stack.pop();
        stack.push(p); // push for future
        p = p.right;
      }
      else {
        // visit p
        result.add(p.val);
        p = null; // next time, don't visit left child
      }
    }
  }
  return result;
}

Time: $O(N)$
Space: $O(h)$