# 94. 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?

```cpp
// Recursion
void helper(TreeNode* root, vector<int>& res) {
    if (!root) return;
    helper(root->left, res);
    res.push_back(root->val);
    helper(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) { // time: O(n); space: O(n)
    vector<int> res;
    helper(root, res);
    return res;
}
```

```cpp
// Iteration
vector<int> inorderTraversal(TreeNode* root) { // time: O(n); space: O(n)
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}
```

{% content-ref url="144.-binary-tree-preorder-traversal" %}
[144.-binary-tree-preorder-traversal](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/144.-binary-tree-preorder-traversal)
{% endcontent-ref %}

{% content-ref url="145.-binary-tree-postorder-traversal" %}
[145.-binary-tree-postorder-traversal](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/145.-binary-tree-postorder-traversal)
{% endcontent-ref %}