Binary Tree Inorder Traversal (Java)

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?

	/*
	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?
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// recursive
	public class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
	ArrayList<Integer> result = new ArrayList<Integer> ();
	if (root == null){
	return result;
	}
	traverse(root, result);
	return result;
	}
	private void traverse(TreeNode root, ArrayList<Integer> result){
	if (root==null){
	return;
	}
	traverse(root.left, result);
	result.add(root.val);
	traverse(root.right, result);
	}
	}
	//iterative solution
	public class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
	ArrayList<Integer> result= new ArrayList<Integer>();
	if (root == null){
	return result;
	}
	Stack<TreeNode> stack = new Stack<TreeNode> ();
	while (root!=null){
	stack.push(root);
	root=root.left;
	}
	while(!stack.isEmpty()){
	TreeNode current = stack.pop();
	result.add(current.val);
	if (current.right != null){
	root=current.right;
	while(root!=null){
	stack.push(root);
	root=root.left;
	}
	}
	}
	return result;
	}
	}

view raw BinaryTreeInorderTraversal.java hosted with ❤ by GitHub