Binary Tree Inorder Traversal

The key to solve inorder traversal of binary tree includes the following:

The order of "inorder" is: left child -> parent -> right child
Use a stack to track nodes
Understand when to push node into the stack and when to pop node out of the stack

Note that inorder traversal of BST is an ascending array.

Algorithm 1 -- Recursive

 1 public class Solution {
 2     List<Integer> result = new ArrayList<Integer>();
 3  
 4     public List<Integer> inorderTraversal(TreeNode root) {
 5         if(root !=null){
 6             helper(root);
 7         }
 8  
 9         return result;
10     }
11  
12     public void helper(TreeNode p){
13         if(p.left!=null)
14             helper(p.left);
15  
16         result.add(p.val);
17  
18         if(p.right!=null)
19             helper(p.right);
20     }
21 }

Algorithm 2 -- Iterative

 1 public class Solution {
 2     public ArrayList<Integer> inorderTraversal(TreeNode root) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5          ArrayList<Integer> lst = new ArrayList<Integer>();
 6  
 7         if(root == null)
 8             return lst; 
 9  
10         Stack<TreeNode> stack = new Stack<TreeNode>();
11         //define a pointer to track nodes
12         TreeNode p = root;
13  
14         while(!stack.empty() || p != null){
15  
16             // if it is not null, push to stack
17             //and go down the tree to left
18             if(p != null){
19                 stack.push(p);
20                 p = p.left;
21  
22             // if no left child
23             // pop stack, process the node
24             // then let p point to the right
25             }else{
26                 TreeNode t = stack.pop();
27                 lst.add(t.val);
28                 p = t.right;
29             }
30         }
31  
32         return lst;
33     }
34 }