> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/binary-tree-inorder-traversal.md).

# 94. Binary Tree Inorder Traversal

### Description

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

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/)
* [Leetcode](https://leetcode.com/problems/binary-tree-inorder-traversal/)
* [ProgramCreek](https://www.programcreek.com/2012/12/leetcode-solution-of-binary-tree-inorder-traversal-in-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[1, null, 2, 3]

1

    \\

        2

    /

3

**Output:** \[1, 3, 2]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```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;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n). The time complexity is O(n) because the recursive 
 *    function is T(n) = 2 * T(n/2) + 1.
 * Space complexity : The worst case space required is O(n), and in the average 
 *    case it's O(logn) where nn is number of nodes.
 */

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        inorder(root, resultList);
        return resultList;
    }
    
    private void inorder(TreeNode root, List<Integer> resultList) {
        if(root == null) return;
        if(root.left != null) {
            inorder(root.left, resultList);
        }
        resultList.add(root.val);
        if(root.right != null) {
            inorder(root.right, resultList);
        }
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n)
 * Space complexity : O(n)
 */

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

{% endtab %}
{% endtabs %}

### **Follow up**

*