Binary Tree Inorder Traversal

Easy· DFS· Stack

Problem

Given the root of a binary tree, return the values of its nodes in inorder: left subtree, then the node, then right subtree. Try to do it both recursively and with an explicit stack.

Examples

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

Output: [1,3,2]

Node 1 has no left child, so it comes first; then its right subtree (2 with left child 3) yields 3 before 2.

Input: root = []

Output: []

Constraints

• 0 <= number of nodes <= 100
• -100 <= Node.val <= 100

Hints & approach

Hint 1

The recursive version is three lines: recurse left, record, recurse right.

Hint 2

To go iterative, simulate the call stack: keep pushing left children until you hit null.

Hint 3

When you pop a node, record it, then move to its right child and repeat the push-left loop.

Approachtry the hints first

Use a stack and a cursor starting at the root. While the cursor is non-null, push it and step to its left child. When the cursor becomes null, pop the top node, append its value, and move the cursor to that node's right child. Repeat until both the stack is empty and the cursor is null. Each node is pushed and popped exactly once.

Time O(n) · Space O(h)

Next →Maximum Depth of Binary Tree