Leetcode Solution of Binary Tree Inorder Traversal in Java

Leetcode Solution of Binary Tree Inorder Traversal in Java
The key to solve inorder traversal of binary tree includes the following:

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

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
         ArrayList<Integer> lst = new ArrayList<Integer>();
 
        if(root == null)
            return lst; 
 
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //define a pointer to track nodes
        TreeNode p = root;
 
        while(!stack.empty() || p != null){
 
            // if it is not null, push to stack
            //and go down the tree to left
            if(p != null){
                stack.push(p);
                p = p.left;
 
            // if no left child
            // pop stack, process the node
            // then let p point to the right
            }else{
                TreeNode t = stack.pop();
                lst.add(t.val);
                p = t.right;
            }
        }
 
        return lst;
    }

Scala version:
https://gist.github.com/23Skidoo/5825875
def inorder_recursive(t : BinaryTree) {
  t match {
    case Node(v, left, right) =>
      inorder_recursive(left)
      print("%d ".format(v))
      inorder_recursive(right)
    case Leaf(v) =>
      print("%d ".format(v))
  }
}

// An iterative solution that uses an explicit stack and will work even for
// very tall trees. Both solutions need O(N) time and O(H) space, where N
// is the size of the tree an H is the height of the tree.
def inorder_iterative(t : BinaryTree) {
  val st = Stack[BinaryTree]()
  st.push(t)
  while (!st.isEmpty) {
    st.pop() match {
      case Node(v, left, right) =>
        st.push(right)
        st.push(Leaf(v))
        st.push(left)
      case Leaf(v) =>
        print("%d ".format(v))
    }
  }
}
Read full article from Leetcode Solution of Binary Tree Inorder Traversal in Java