Binary Tree Postorder Traversal

Problem

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

Example

Given binary tree {1,#,2,3},

1
 \
  2
 /
3

return [3,2,1].

Challenge

Can you do it without recursion?

Solution

With Recursion

Traverse the left node, then the right node, then the current node.

void traverse(TreeNode node, ArrayList<Integer> result) {
  if (node == null) {
    return;
  }
  traverse(node.left, result);
  traverse(node.right, result);
  result.add(node.val);
}

Without Recursion

Postorder is equivalent to the reverse order of (current, right, left), so we can modify the preorder traversal to append left node first, and at the end reverse the result list.