Binary Tree Inorder Traversal

Easy Problem 62 of 151 Java and Python

Problem

Given the root of a binary tree, return the inorder traversal of its values: the left subtree, then the node, then the right subtree.

Example 1

Input: root = [1, null, 2, 3]
Output: [1, 3, 2]
Why: 1 has no left child; its right child 2 has left child 3.

Example 2

Input: root = []
Output: []

Constraints

0 ≤ number of nodes ≤ 100
Follow-up: do it iteratively.

Explanation

Recursion mirrors the definition directly: visit left, record the node, visit right.

The iterative version simulates the call stack: keep going left while pushing nodes; when you cannot go further, pop a node, record it, and continue from its right child.

Approach 1 · Naive

Recursion

Time O(n)
Space O(h) call stack, h = height

A helper visits the left subtree, adds the node, then visits the right subtree.

If the node is null, return.
Recurse left, add node.val, recurse right.

Java

import java.util.*;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        visit(root, result);
        return result;
    }

    private void visit(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        visit(node.left, result);
        result.add(node.val);
        visit(node.right, result);
    }
}

Python

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

        def visit(node):
            if node:
                visit(node.left)
                result.append(node.val)
                visit(node.right)

        visit(root)
        return result

Approach 2 · Optimal

Iterative with a stack

Time O(n)
Space O(h)

Push nodes while walking left. Pop one, record it, then move to its right child.

Set curr = root and an empty stack.
While curr or the stack is not empty: push and go left until curr is null.
Pop a node, record it, set curr = node.right.

Java

import java.util.*;

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

Python

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

Complexity compared

Approach	Time	Space
Naive Recursion	O(n)	O(h) call stack, h = height
Optimal Iterative with a stack	O(n)	O(h)

Key takeaways

Inorder of a binary search tree is sorted, which many BST problems rely on.
Morris traversal does it in O(1) space by temporarily threading right pointers; worth knowing it exists.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem