# Binary Tree Inorder Traversal
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-tree-inorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-inorder-traversal
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Stack, Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber)
---
## Problem
Given the `root` of a binary tree, return _the inorder traversal of its nodes' values_.

**Example 1:**

**Input:** root = \[1,null,2,3\]

**Output:** \[1,3,2\]

**Explanation:**

![](https://assets.glich.co/dsa/binary-tree-inorder-traversal/image0.png)

**Example 2:**

**Input:** root = \[1,2,3,4,5,null,8,null,null,6,7,9\]

**Output:** \[4,2,6,5,7,1,3,9,8\]

**Explanation:**

![](https://assets.glich.co/dsa/binary-tree-inorder-traversal/image1.png)

**Example 3:**

**Input:** root = \[\]

**Output:** \[\]

**Example 4:**

**Input:** root = \[1\]

**Output:** \[1\]

**Constraints:**

* The number of nodes in the tree is in the range `[0, 100]`.
* `-100 <= Node.val <= 100`

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

# Approaches
## Recursive Inorder Traversal
This is the most straightforward and intuitive approach. The structure of the recursive algorithm directly mirrors the definition of an inorder traversal (Left, Root, Right). We create a helper function that is called recursively on the left child, then processes the current node, and finally is called on the right child.
**Time:** O(N), where N is the number of nodes in the tree, because we visit each node exactly once. · **Space:** O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N), where N is the number of nodes. In the best case of a balanced tree, it's O(log N). This space is used by the recursion call stack.
**Pros:** The code is simple, clean, and easy to understand as it directly follows the definition of inorder traversal.; It requires minimal code to implement.
**Cons:** For very deep or skewed trees, this can lead to a `StackOverflowError` because the depth of the recursion call stack can exceed its limit.; The space used by the call stack is implicit and not directly controlled by the programmer.
### Explanation
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }

    private void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 1. Traverse the left subtree
        inorderHelper(node.left, result);
        // 2. Visit the root node
        result.add(node.val);
        // 3. Traverse the right subtree
        inorderHelper(node.right, result);
    }
}
```
### Algorithm
The core idea of inorder traversal is to visit nodes in the order: Left Subtree, Root, Right Subtree. A recursive function naturally models this process.

1.  Define a helper function, let's say `inorderHelper(TreeNode node, List<Integer> result)`.
2.  The base case for the recursion is when the `node` is `null`. In this case, we simply return.
3.  If the node is not `null`:
    a. Make a recursive call on the left child: `inorderHelper(node.left, result)`.
    b. After the left subtree has been fully traversed, visit the current node by adding its value to the result list: `result.add(node.val)`.
    c. Finally, make a recursive call on the right child: `inorderHelper(node.right, result)`.
4.  The main function initializes an empty list and calls the helper function with the root of the tree.

## Iterative Inorder Traversal using a Stack
To avoid the potential for stack overflow from deep recursion, we can perform the traversal iteratively using an explicit stack. This approach mimics the behavior of the recursion call stack. We keep pushing left children onto the stack until we can't go further left. Then, we pop a node, process it, and move to its right child.
**Time:** O(N), as each node is pushed onto and popped from the stack exactly once. · **Space:** O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N). In the best case of a balanced tree, it's O(log N). This space is used by the explicit stack.
**Pros:** It avoids recursion, thus eliminating the risk of a `StackOverflowError` for very deep trees.; It can be more efficient in languages where function calls have high overhead.
**Cons:** The logic is slightly more complex to write and understand compared to the recursive version.; It still requires extra space for the stack, which can be significant for skewed trees.
### Explanation
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // Go as far left as possible
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // Backtrack from the empty subtree, visit the node at the top of the stack
            current = stack.pop();
            result.add(current.val);

            // Now, visit the right subtree
            current = current.right;
        }

        return result;
    }
}
```
### Algorithm
This method simulates the recursive approach using an explicit stack to keep track of the nodes.

1.  Initialize an empty `List<Integer>` for the result and an empty `Stack<TreeNode>`.
2.  Create a `TreeNode` pointer, `current`, and initialize it to `root`.
3.  Loop as long as `current` is not `null` or the `stack` is not empty.
4.  Inside the loop, push all the left children onto the stack: while `current` is not `null`, push `current` to the stack and update `current` to `current.left`.
5.  Once `current` becomes `null`, it means we have reached the leftmost node of the current subtree. Now, we process the node at the top of the stack.
6.  Pop a node from the stack, let this be the new `current`.
7.  Add the value of the popped node to the result list: `result.add(current.val)`.
8.  Move to the right child of the popped node: `current = current.right`. This will start the process for the right subtree in the next iteration of the main loop.

## Morris Inorder Traversal (Threaded Tree)
This is the most space-efficient approach. The key idea is to create temporary links (or "threads") in the tree to keep track of where to go next, eliminating the need for a stack or recursion. For each node, we find its inorder predecessor (the rightmost node in its left subtree). We use the predecessor's `right` pointer (which would normally be `null`) to point back to the current node. This thread allows us to return to the current node after traversing its entire left subtree. Once we return, we visit the current node, remove the thread, and move to the right subtree.
**Time:** O(N). Although we seem to traverse some parts of the tree multiple times, a closer analysis shows that each edge is traversed at most twice (once to go down, and once to come back up via the thread). Therefore, the total time complexity is linear. · **Space:** O(1). No extra space is used besides a few pointers to traverse the tree.
**Pros:** Extremely space-efficient, achieving O(1) auxiliary space.; It does not use recursion, so there is no risk of stack overflow.
**Cons:** The algorithm is much more complex to understand and implement correctly.; It temporarily modifies the tree structure. This can be problematic in a multi-threaded environment if the tree is shared, as it would require locking mechanisms.
### Explanation
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode current = root;
        TreeNode pre;

        while (current != null) {
            if (current.left == null) {
                result.add(current.val); // Visit node
                current = current.right; // Move to right
            } else {
                // Find the inorder predecessor of current
                pre = current.left;
                while (pre.right != null && pre.right != current) {
                    pre = pre.right;
                }

                if (pre.right == null) {
                    // Create the thread
                    pre.right = current;
                    current = current.left;
                } else {
                    // Thread exists, so we've visited the left subtree
                    // Remove the thread
                    pre.right = null;
                    result.add(current.val); // Visit node
                    current = current.right; // Move to right
                }
            }
        }
        return result;
    }
}
```
### Algorithm
Morris Traversal modifies the tree on the fly to create links (threads) to inorder successors, and then reverts the changes. This allows traversal without a stack or recursion.

1.  Initialize a `current` pointer to `root` and an empty list `result`.
2.  While `current` is not `null`:
    a. If `current` has no left child:
        i.  Visit `current` by adding its value to `result`.
        ii. Move to the right child: `current = current.right`.
    b. If `current` has a left child:
        i.  Find the inorder predecessor of `current`. The predecessor is the rightmost node in the left subtree of `current`. Let's call it `pre`.
        ii. If the right child of `pre` is `null` (we haven't created a thread yet):
            - Create a thread from `pre` to `current`: `pre.right = current`.
            - Move `current` to its left child to traverse the left subtree: `current = current.left`.
        iii. If the right child of `pre` is `current` (a thread exists, meaning we've finished traversing the left subtree):
            - Remove the thread to restore the tree's original structure: `pre.right = null`.
            - Visit `current` by adding its value to `result`.
            - Move to the right child: `current = current.right`.

# Solutions
### Java

```java
import java.util.ArrayList ; import java.util.HashSet ; import java.util.List ; import java.util.Stack ; public class Binary_Tree_Inorder_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution_optmize { public List < Integer > inorderTraversal ( TreeNode root ) { List < Integer > list = new ArrayList < Integer >(); if ( root == null ) { return list ; } Stack < TreeNode > sk = new Stack <>(); TreeNode current = root ; while (! sk . isEmpty () || current != null ) { while ( current != null ) { sk . push ( current ); current = current . left ; } // @note: 一逼撸到最左边 // @note: 没有push left的操作，就不会无限循环，也不需要mark是否visited TreeNode leftOrMiddle = sk . pop (); list . add ( leftOrMiddle . val ); current = leftOrMiddle . right ; // if right is null here, next time pop parent node } return list ; } } class Solution_noStack { // but modifying original tree public List < Integer > inorderTraversal ( TreeNode root ) { List < Integer > result = new ArrayList <>(); TreeNode current = root ; TreeNode prev ; while ( current != null ) { if ( current . left == null ) { result . add ( current . val ); // only handle right child current = current . right ; // move to next right node } else { // has a left subtree prev = current . left ; while ( prev . right != null ) { // find rightmost prev = prev . right ; } prev . right = current ; // put cur after the pre node TreeNode temp = current ; // store cur node current = current . left ; // move cur to the top of the new tree temp . left = null ; // original cur left be null, avoid infinite loops } } return result ; } } public class Solution { List < Integer > list = new ArrayList < Integer >(); public List < Integer > inorderTraversal ( TreeNode root ) { // mark if a node is visited already: true is visited. or, just use a Set HashSet < TreeNode > hs = new HashSet <>(); Stack < TreeNode > sk = new Stack <>(); sk . push ( root ); while (! sk . isEmpty ()) { TreeNode current = sk . pop (); if ( current == null ) { continue ; } // @note: careful to check left visited, or else infinite looping if ( current . left != null && ! hs . contains ( current . left )) { sk . push ( current ); sk . push ( current . left ); } else { if ( current . right != null && ! hs . contains ( current . right )) { sk . push ( current . right ); } hs . add ( current ); list . add ( current . val ); } } return list ; } } class Solution_recursion { List < Integer > result = new ArrayList <>(); public List < Integer > inorderTraversal ( TreeNode root ) { dfs ( root ); return result ; } public void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); result . add ( root . val ); dfs ( root . right ); } } } ////// /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > inorderTraversal ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); while ( root != null ) { if ( root . left == null ) { ans . add ( root . val ); root = root . right ; } else { TreeNode prev = root . left ; while ( prev . right != null && prev . right != root ) { prev = prev . right ; } if ( prev . right == null ) { prev . right = root ; root = root . left ; } else { ans . add ( root . val ); prev . right = null ; root = root . right ; } } } return ans ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var inorderTraversal =
  function (root) {
    let ans = [];
    while (root) {
      if (!root.left) {
        ans.push(root.val);
        root = root.right;
      } else {
        let prev = root.left;
        while (prev.right && prev.right != root) {
          prev = prev.right;
        }
        if (!prev.right) {
          prev.right = root;
          root = root.left;
        } else {
          ans.push(root.val);
          prev.right = null;
          root = root.right;
        }
      }
    }
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < int > inorderTraversal ( TreeNode * root ) { vector < int > ans ; while ( root ) { if ( ! root -> left ) { ans . push_back ( root -> val ); root = root -> right ; } else { TreeNode * prev = root -> left ; while ( prev -> right && prev -> right != root ) { prev = prev -> right ; } if ( ! prev -> right ) { prev -> right = root ; root = root -> left ; } else { ans . push_back ( root -> val ); prev -> right = nullptr ; root = root -> right ; } } } return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def inorderTraversal ( self , root : Optional [ TreeNode ]) -> List [ int ]: stack = [] current = root res = [] while stack or current : while current : stack . append ( current ) current = current . left left_or_middle = stack . pop () res . append ( left_or_middle . val ) current = left_or_middle . right return res # no stack, but modifying original tree class Solution : def inorderTraversal ( self , root ): result = [] current = root prev = None while current : if current . left is None : result . append ( current . val ) current = current . right else : prev = current . left while prev . right : prev = prev . right prev . right = current temp = current current = current . left temp . left = None return result class Solution : def inorderTraversal ( self , root : Optional [ TreeNode ]) -> List [ int ]: ans = [] while root : if root . left is None : ans . append ( root . val ) root = root . right else : prev = root . left while prev . right and prev . right != root : prev = prev . right if prev . right is None : prev . right = root root = root . left else : ans . append ( root . val ) prev . right = None root = root . right return ans ########### # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None ''' >>> stack = [(1, None)] >>> stack.extend([(0, None), (2, "b"), (3, "c")]) >>> stack [(1, None), (0, None), (2, 'b'), (3, 'c')] ''' class Solution ( object ): def inorderTraversal ( self , root ): """ :type root: TreeNode :rtype: List[int] """ # stack to hold tuple (), '0' meaning a parent node for current level, '1' meaning a child node res , stack = [], [( 1 , root )] while stack : p = stack . pop () if not p [ 1 ]: continue stack . extend ([( 1 , p [ 1 ]. right ), ( 0 , p [ 1 ]), ( 1 , p [ 1 ]. left )]) if p [ 0 ] != 0 else res . append ( p [ 1 ]. val ) return res
```