Binary Tree Preorder Traversal

Problem

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

Example

Given:

        1
       / \
      2   3
     / \
    4   5

return [1,2,4,5,3].

Challenge

Can you do it without recursion?

Solution

With Recursion

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

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

Without Recursion

Use a stack, initialize the stack with the root, then loop until the stack is empty.

For each popped node, add the right node first, then the left node, so the the left node will be popped first.