Binary Tree Inorder Traversal

Problem

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

Example

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

   1
    \
     2
    /
   3

return [1,3,2].

Challenge

Can you do it without recursion?

Solution

With recursion

The key of "inorder" is to traverse the left tree, then current node, then the right tree:

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

Without recursion

Use a stack.

Create a helper method addNodes() to add a node and its left child nodes to the stack.

Initialize the stack by calling addNodes(root).

While the stack is not empty, pop a node, add it to the result, and call addNodes() on its right child.

This is the same as Binary Search Tree Iterator.