Binary Tree Inorder Traversal Solution Explained

Data Structures / Tree

Binary Tree Inorder Traversal

Easy

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

Example

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

Tree Structure:

      1

       \

        2

       /

      3

Explanation: Inorder traversal visits left subtree, then root, then right subtree.

Understanding Inorder Traversal

Before diving into the solution, let's understand what inorder traversal means:

Left subtree: Traverse the entire left subtree first
Root node: Visit/process the root node
Right subtree: Traverse the entire right subtree last

This pattern (Left → Root → Right) is applied recursively to every node in the tree. For a Binary Search Tree (BST), this produces nodes in sorted order!

Visual Example: For the tree above:

Start at root (1) - go left (nothing there)
Visit root: 1
Go right to node 2 - go left to node 3
At node 3 - go left (nothing), visit: 3, go right (nothing)
Back at node 2 - visit: 2, go right (nothing)
Result: [1, 3, 2]

Approach 1: Recursive Solution

The recursive approach follows the natural definition of inorder traversal:

Base case: If node is null, return empty list
Recursively traverse the left subtree and get its result
Add the current node's value to the result
Recursively traverse the right subtree and get its result
Combine: left_result + [current_value] + right_result

The call stack naturally handles the "backtracking" - when we finish with a subtree, we return to the parent node.

Approach 2: Iterative Solution with Stack

The iterative approach simulates the recursive call stack using an explicit stack data structure:

Start with the root node and an empty stack
Go as left as possible, pushing each node onto the stack
When you can't go left anymore, pop from the stack (this is the next node to visit)
Add the popped node's value to the result
Move to the right subtree and repeat

This approach gives you more control and avoids potential stack overflow for very deep trees.

Idea Map

Start at Root

Push all left nodes to stack

Pop node → add value to result

Go to right child, repeat

Continue until stack is empty AND current is null

Return Result

Complexity Analysis

Time Complexity

O(n) - We visit each node exactly once, where n is the number of nodes.

Space Complexity

O(h) - Stack depth equals tree height h. Worst case O(n) for skewed tree, O(log n) for balanced tree.

Code - Recursive Solution


def inorderTraversal(root):
Initializes the function `inorderTraversal` which takes the `root` of a binary tree as input.
    result = []
Creates an empty list to store the inorder traversal result.
    def inorder(node):
Defines a nested helper function `inorder` that performs the recursive traversal.
        if not node:
Base case: if the node is None (null), return without doing anything.
            return
Return from the recursive call when we reach a null node.
        inorder(node.left)
First: recursively traverse the entire left subtree.
        result.append(node.val)
Second: add the current node's value to the result list.
        inorder(node.right)
Third: recursively traverse the entire right subtree.
    inorder(root)
Start the traversal by calling the helper function on the root node.
    return result
Return the complete inorder traversal result.


public List<Integer> inorderTraversal(TreeNode root) {
Initializes the function `inorderTraversal` which takes the `root` of a binary tree as input.
    List<Integer> result = new ArrayList<>();
Creates an ArrayList to store the inorder traversal result.
    inorder(root, result);
Starts the traversal by calling the helper function with root and result list.
    return result;
Return the complete inorder traversal result.
}
End of the main function.
private void inorder(TreeNode node, List<Integer> result) {
Helper function that takes a node and the result list for recursive traversal.
    if (node == null) return;
Base case: if node is null, return immediately.
    inorder(node.left, result);
First: recursively traverse the entire left subtree.
    result.add(node.val);
Second: add the current node's value to the result list.
    inorder(node.right, result);
Third: recursively traverse the entire right subtree.
}
End of the helper function.


vector<int> inorderTraversal(TreeNode* root) {
Initializes the function `inorderTraversal` which takes a pointer to the `root` of a binary tree.
    vector<int> result;
Creates a vector to store the inorder traversal result.
    inorder(root, result);
Starts the traversal by calling the helper function with root and result vector.
    return result;
Return the complete inorder traversal result.
}
End of the main function.
void inorder(TreeNode* node, vector<int>& result) {
Helper function that takes a node pointer and reference to result vector.
    if (!node) return;
Base case: if node is nullptr, return immediately.
    inorder(node->left, result);
First: recursively traverse the entire left subtree.
    result.push_back(node->val);
Second: add the current node's value to the result vector.
    inorder(node->right, result);
Third: recursively traverse the entire right subtree.
}
End of the helper function.

Code - Iterative Solution


def inorderTraversal(root):
Initializes the iterative inorder traversal function.
    result = []
Creates an empty list to store the traversal result.
    stack = []
Creates an empty stack to simulate the recursive call stack.
    current = root
Initialize current pointer to the root of the tree.
    while current or stack:
Continue while there are nodes to process (current exists or stack not empty).
        while current:
Go as far left as possible from the current node.
            stack.append(current)
Push the current node onto the stack (to visit it later).
            current = current.left
Move to the left child of current node.
        current = stack.pop()
Pop the top node from stack (this is the next node to visit in inorder).
        result.append(current.val)
Add the popped node's value to the result list.
        current = current.right
Move to the right subtree to process it next.
    return result
Return the complete inorder traversal result.


public List<Integer> inorderTraversal(TreeNode root) {
Initializes the iterative inorder traversal function.
    List<Integer> result = new ArrayList<>();
Creates an ArrayList to store the traversal result.
    Deque<TreeNode> stack = new ArrayDeque<>();
Creates a Deque (double-ended queue) to use as a stack.
    TreeNode current = root;
Initialize current pointer to the root of the tree.
    while (current != null || !stack.isEmpty()) {
Continue while there are nodes to process.
        while (current != null) {
Go as far left as possible from the current node.
            stack.push(current);
Push the current node onto the stack.
            current = current.left;
Move to the left child of current node.
        }
End of inner while loop.
        current = stack.pop();
Pop the top node from stack.
        result.add(current.val);
Add the popped node's value to the result list.
        current = current.right;
Move to the right subtree.
    }
End of outer while loop.
    return result;
Return the complete inorder traversal result.
}
End of the function.


vector<int> inorderTraversal(TreeNode* root) {
Initializes the iterative inorder traversal function.
    vector<int> result;
Creates a vector to store the traversal result.
    stack<TreeNode*> st;
Creates a stack to store TreeNode pointers.
    TreeNode* current = root;
Initialize current pointer to the root of the tree.
    while (current || !st.empty()) {
Continue while there are nodes to process.
        while (current) {
Go as far left as possible from the current node.
            st.push(current);
Push the current node onto the stack.
            current = current->left;
Move to the left child of current node.
        }
End of inner while loop.
        current = st.top();
Get the top node from stack (but don't pop yet).
        st.pop();
Pop the top node from stack.
        result.push_back(current->val);
Add the popped node's value to the result vector.
        current = current->right;
Move to the right subtree.
    }
End of outer while loop.
    return result;
Return the complete inorder traversal result.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Empty tree (null root)

Always handle the case where the root is null. Both recursive and iterative solutions handle this naturally - just return an empty list.

💡

Stack overflow with recursion

For very deep trees (skewed trees), recursion can cause stack overflow. Use the iterative approach to avoid this issue.

✓

Single node tree

A tree with only one node should return a list with just that node's value. The traversal is: left (none) → root → right (none).

What is Tree Traversal?

Tree traversal is the process of visiting each node in a tree exactly once. Inorder traversal is one of the Depth-First Search (DFS) methods, following the Left → Root → Right pattern. For Binary Search Trees, inorder traversal produces sorted output!

Learn more about tree traversals →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Binary Tree Inorder Traversal' problem on LeetCode.

AlgoExplained.dev