EasyStackTreeDepth-First SearchBinary Tree

Binary Tree Inorder Traversal

2 approaches, code in every language

You are given the root of a binary tree. Return the values of its nodes visited in inorder sequence.

An inorder traversal processes each subtree in the order left child, then the node itself, then right child. Applied recursively from the root, this rule produces a single flat list of every value in the tree.

For a binary search tree, this ordering happens to yield the values sorted ascending, but the traversal itself is defined purely by the left-node-right visiting rule and works for any binary tree.

Example 1

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

Output: [1,3,2]

The root 1 has no left child, so 1 is emitted first. Its right child 2 has left child 3, so we descend, emit 3, then 2.

Example 2

Input: root = [1,2,3,4,5]

Output: [4,2,5,1,3]

Node 1 has left subtree rooted at 2 (children 4 and 5) and right child 3. Inorder of the left subtree is 4,2,5, then the root 1, then 3.

Constraints

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

Recursive DFS

Follow the definition directly: recurse left, record the node, recurse right.

Loading animation…

Intuition

Inorder traversal is defined recursively, so the most natural solution mirrors that definition. For any node, we first fully traverse its left subtree, then append the node's own value, then fully traverse its right subtree. The base case is a null pointer, which contributes nothing. Because each node delegates the work on its children to the same function, the call stack manages all the bookkeeping for us. This makes the code short and easy to trust.

Algorithm walkthrough

1Create an empty result list that the recursion will fill in order.
2Define a helper that takes a node and returns immediately when the node is null.
3Recurse into the node's left child first so the entire left subtree is emitted before the node.
4Append the current node's value to the result list.
5Recurse into the node's right child to emit the right subtree after the node.
6Invoke the helper on the root and return the accumulated list.

Implementation

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result: List[int] = []

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)

        dfs(root)
        return result

Time

O(n)

Space

O(h)

Each of the n nodes is visited exactly once. The recursion stack grows to the tree height h, which is O(n) for a skewed tree and O(log n) when balanced.

Iterative with Explicit Stack

Simulate the recursion by pushing every left child onto a stack, then unwind.

Loading animation…

Intuition

The recursive version is elegant but hides a stack inside the runtime; we can make that stack explicit to avoid recursion. The key insight is that before we can record any node, we must first walk as far left as possible, remembering each node we pass. Once the left spine is exhausted, the most recently pushed node is the leftmost unvisited node, so we pop it, record it, and then pivot to its right child. Repeating this until both the stack and the current pointer are empty reproduces the exact left-node-right order.

Algorithm walkthrough

1Keep an empty stack and a current pointer starting at the root.
2While the current pointer is non-null, push it and move to its left child, walking down the left spine.
3When the current pointer becomes null, pop the top of the stack; this is the next node in inorder.
4Append the popped node's value to the result.
5Set the current pointer to the popped node's right child so its right subtree is processed next.
6Stop when both the stack is empty and the current pointer is null, then return the result.

Implementation

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result: List[int] = []
        stack: List[TreeNode] = []
        current = root
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right
        return result

Time

O(n)

Space

O(h)

Every node is pushed and popped once. The stack holds at most one full root-to-leaf left spine, so its size is bounded by the tree height h.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Manifold Valve Readout is our own problem on the technique behind Binary Tree Inorder Traversal: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free