Binary Tree In-order Traversal

Today LeetCode has new problems about binary search trees. Thanks leetcode!

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].

Note: Recursive solution is trivial, could you do it iteratively?

We first look the recursive solution.

The tree node is defined as,

Java: TreeNode

1 public class TreeNode {

2     int val;

3     TreeNode left;

4     TreeNode right;

5     TreeNode(int x) { val = x; }

6 }

Then we write the in-order traversal method

Java: BSTInOderRecursion

01 public ArrayList<Integer> inorderTraversal(TreeNode root) {

02     ArrayList<Integer> result=new ArrayList<Integer>();

03     inorder(result,root);

04     return result;

05 }

06 

07 public void inorder(ArrayList<Integer> result,TreeNode root)

08 {

09     if(root==null)

10         return;

11     

12     if(root.left!=null)

13     {

14         inorder(result,root.left);

15     }

16     

17     result.add(root.val);

18     

19     if(root.right!=null)

20     {

21         inorder(result,root.right);

22     }

23 }

However, we can also solve it  iteratively. This can be done with the help of a stack. We add from root each node on the left to the stack, until we do not find a left node in the end. If the stack is not empty, we pop a node from it and print it. If the popped node has right child, we add it to the stack and track it to the left most node, until we cannot find a left node any more.

Java: BSTInOrder

01 public ArrayList<Integer> inorderTraversal(TreeNode root) {

02     ArrayList<Integer> result=new ArrayList<Integer>();

03     Stack<TreeNode> st=new Stack<TreeNode>();

04     if(root!=null)

05     {

06         st.push(root);

07         while(root.left!=null)

08         {

09             root=root.left;

10             st.push(root);

11         }

12     }

13     while(!st.empty())

14     {

15         TreeNode top=st.pop();

16         result.add(top.val);

17         if(top.right!=null)

18         {

19             st.push(top.right);

20             top=top.right;

21             while(top.left!=null)

22             {

23                 top=top.left;

24                 st.push(top);

25             }

26         }

27     }

28   

29     return result;

30 }

I believe there are solutions even without using a Stack. Please feel free to show your ideas.