Binary Tree Inorder Traversal

Problem:

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Analysis:

The definition of inorder traversal is visit the left node first, the parent node second and the right node last. Iterative implementation of inorder traversal is more difficult than preorder traversal. We need to consider how to visit the left most node and keep track of the trace.

1. Push the root node to the stack.

2. Set the left child of the current node to the current node.

3. Continue 1,2 until current node is null.

4. If current node is not null.

   1). Pop current node from the stack and write it.

   2). Set the right child of the current node to the current node. go to 2.

5. If the stack is empty return. 

Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<Integer> inorderTraversal(TreeNode root) {  
12:      ArrayList<Integer> result=new ArrayList<Integer>();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> stack=new Stack<TreeNode>();  
16:      TreeNode current=root;  
17:      while(true)  
18:      {  
19:        if(current!=null)//iterate left until there is no left node at all       
20:        {  
21:         stack.push(current);  
22:         current=current.left;  
23:        }  
24:        else  
25:        {  
26:          if(!stack.isEmpty())  
27:          {  
28:            current=stack.pop();  
29:            result.add(current.val);  
30:            current=current.right;//have visited the left and the parent node, time to visit the right one.  
31:          }  
32:          else  
33:           break;  
34:        }  
35:      }  
36:      return result;  
37:    }  
38:  }