Binary Tree Inorder Traversal

Tree
DFS
Recursion

Given the root of a binary tree, return the in-order traversal of its node values (Left → Root → Right).

The recursive solution is the cleanest: traverse the left subtree, visit the current node, then traverse the right subtree. An iterative version uses an explicit stack to mimic the call frames.

Examples

Example 1

Input

root

Output

1

3

2

Example 2

Input

root

(empty tree)

Output

Example 3

Input

root

Output

1

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
-100 ≤ Node.val ≤ 100

Stuck? Hint 1

Recurse left, append current value, recurse right.

Input

Expected Output

1

3

2

Ctrl / ⌘ + Enter

Binary Tree Inorder Traversal

Tree
DFS
Recursion

Given the root of a binary tree, return the in-order traversal of its node values (Left → Root → Right).

The recursive solution is the cleanest: traverse the left subtree, visit the current node, then traverse the right subtree. An iterative version uses an explicit stack to mimic the call frames.

Examples

Example 1

Input

root

Output

1

3

2

Example 2

Input

root

(empty tree)

Output

Example 3

Input

root

Output

1

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
-100 ≤ Node.val ≤ 100

Stuck? Hint 1

Recurse left, append current value, recurse right.

Input

Expected Output

1

3

2

Ctrl / ⌘ + Enter