> For the complete documentation index, see [llms.txt](https://a.b.cr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://a.b.cr/dictionary/algorithm/diary/2022/06/2022-06-30.md).

# 2022-06-30

## [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)

### Description

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

**Example 1:**

![](https://img.content.cc/a/2022/06/30/16-03-37-558-680cedc2eafece9406e0b00f9958fdf5-aee3a8.png)

```
Input: root = [1,null,2,3]
Output: [1,3,2]
```

**Example 2:**

```
Input: root = []
Output: []
```

**Example 3:**

```
Input: root = [1]
Output: [1]
```

**Constraints:**

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

### Solution

#### Approach #0: **Recursive**

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        ans = append(ans, node.Val)
        dfs(node.Right)
    }
    dfs(root)
    return
}
```

#### Approach #1: **Iterative**

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
    st := []*TreeNode{}
    for root != nil || len(st) > 0 {
        for root != nil {
            st = append(st, root)
            root = root.Left
        }
        root = st[len(st)-1]
        st = st[:len(st)-1]
        ans = append(ans, root.Val)
        root = root.Right
    }
    return
}
```