# 94. Binary Tree Inorder Traversal

[Link](https://leetcode.com/problems/binary-tree-inorder-traversal/)

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

**Example:**

```
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
```

**Follow up:** Recursive solution is trivial, could you do it iteratively?

**Solution**

Idea:&#x20;

1. Use stack to record treeNode in order, be sure the last one will be the first traveled
2. push all all root's left node (including it's self) for each node with correct order
3. when a node in stack is handled (i.e, updated to ret), do step 2 for it's right side node

```
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        while(root != null||!stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ret.add(root.val);
            root = root.right;
        }
        return ret;
    }
}
```
