Tech Blogs LLD SDE Playbook DSA

Binary Tree Inorder Traversal

Easy Top 250
Associated Patterns
Trees
Interviewed At (Company Tags)
GoogleAmazonMicrosoft
External Reference View on LeetCode

Problem Description

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

Examples

Example 1:

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

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [1] Output: [1]

Constraints

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

Left, Root, Right Traversal order

Inorder traversal visits a binary tree in the order: Left Subtree -> Root Node -> Right Subtree. We can solve this:

  1. Recursively: Call the helper function on the left child, visit the root node, and then call the helper on the right child.
  2. Iteratively: Use a stack to track parent nodes. We traverse down the left branch of the tree, pushing nodes onto the stack, until we reach a null node. Then, we pop a node from the stack, record its value, and shift our focus to its right child, repeating the left-down traversal.

Solution 1: Recursive Inorder Traversal

Recursively traverse left subtree, record parent value, then traverse right subtree.

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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

    private void traverse(TreeNode node, List<Integer> list) {
        if (node == null) return;
        traverse(node.left, list);  // left
        list.add(node.val);         // root
        traverse(node.right, list); // right
    }
}
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        result = []
        
        def traverse(node: Optional[TreeNode]):
            if not node:
                return
            traverse(node.left)    # left
            result.append(node.val) # root
            traverse(node.right)   # right

        traverse(root)
        return result
#include <vector>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
private:
    void traverse(TreeNode* node, std::vector<int>& list) {
        if (!node) return;
        traverse(node->left, list);
        list.push_back(node->val);
        traverse(node->right, list);
    }

public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        traverse(root, result);
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we visit every node exactly once.
  • Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

Solution 2: Iterative Traversal using Stack

Use an explicit stack to trace left branches and back up to parent nodes.

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr); // cache parents
                curr = curr.left; // go deep left
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right; // check right child
        }
        return result;
    }
}
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  # go deep left
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right  # check right child
            
        return result
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> stack;
        TreeNode* curr = root;

        while (curr || !stack.empty()) {
            while (curr) {
                stack.push(curr);
                curr = curr->left;
            }
            curr = stack.top();
            stack.pop();
            result.push_back(curr->val);
            curr = curr->right;
        }
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we process every node once.
  • Space Complexity: O(h) auxiliary space where h is the height of the tree, representing the maximum elements stored in the stack.

Where It Breaks

If the tree is modified concurrently during traversal, both recursive and iterative stack models will become corrupted.

Common Mistakes

  • Incorrect check loops: Forgetting !stack.isEmpty() in the main loop condition, causing the iteration to stop prematurely at the first leaf node.
  • Dangling references: Moving the current pointer to curr.left inside the pop block instead of curr.right.

← All Problems