# 94. Binary Tree Inorder Traversal (Medium)

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?

## Solutions

``````class Solution {

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();

if (root == null) {
return ans;
}

Stack<TreeNode> stack = new Stack<>();

TreeNode tmp = root;

while (tmp != null || !stack.isEmpty()) {

// keep all the left nodes into the stack
while (tmp != null) {
stack.push(tmp);

tmp = tmp.left;
}

tmp = stack.pop();

// visit the element value after pop

// find a valid right node to traverse its left nodes
while (!stack.isEmpty() && tmp.right == null) {
tmp = stack.pop();

// visit the element value after pop
}

// reach here, stack empty or tmp.right != null

tmp = tmp.right;
}

return ans;
}
}
``````