What is the time complexity of Binary Tree Inorder Traversal?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Binary Tree Inorder Traversal?

This problem uses Stack, Tree, Depth-First Search, Binary Tree. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Binary Tree Inorder Traversal?

An iterative Depth-First Search (DFS) for inorder traversal meticulously simulates the recursive call stack by using an explicit stack to store nodes whose left subtrees are yet to be fully explored. This allows us to defer processing a node's value until its entire left subtree has been visited. The pattern of `while curr: stack.append(curr); curr = curr.left` is paramount. It ensures that we always push nodes onto the stack as we dive deep into the leftmost branch. The stack then acts as a 'breadcrumb trail' of parent nodes waiting for their left children to be fully processed.

Which companies ask LeetCode 94. Binary Tree Inorder Traversal in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Meta and 2 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Binary Tree Inorder Traversal - LeetCode 94 Solution

Q: How to solve Binary Tree Inorder Traversal?

The provided solution implements an iterative Depth-First Search (DFS) for inorder traversal, cleverly circumventing explicit recursion by using an auxiliary stack. The core idea is to simulate the recursive call stack: we continuously descend down the left child path, pushing each visited node onto the stack. These stacked nodes represent ancestors whose left subtrees we're currently exploring, and whose values we haven't yet 'processed'. When we finally hit a `null` node (meaning we've gone as far left as possible in the current subtree), we know the leftmost node's left subtree is fully explored. It's then time to pop a node from the stack. This popped node is the 'current root' that we need to process (add its value to our result). Crucially, after processing this node, we immediately set `curr` to its *right* child. This ensures that the next iteration of the outer `while` loop will either continue descending left from this new `curr` (if it's not null), or, if it's null, we'll pop the next pending ancestor from the stack to process its value and then explore its right subtree. This loop continues until both `curr` is null and the stack is empty, meaning all nodes have been visited.

Binary Tree Inorder Traversal - Complete Solution Guide

Binary Tree Inorder Traversal is LeetCode problem 94, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values . Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,2,6,5,7,1,3,9,8] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] Constraints: The number of nodes in the tree is in the range [0, 100] . -100 <= Node.val <= 100 Follow up: Recursive solution is trivial, could you do it iteratively?

Detailed Explanation

This problem asks us to perform an 'inorder' traversal on a given binary tree and return a list of its node values in that specific order. 'Inorder' isn't just visiting nodes from left to right; it defines a precise sequence for each node: first, recursively traverse its *entire left subtree*, then visit the node itself (add its value to our result), and finally, recursively traverse its *entire right subtree*. This recursive definition applies consistently across every node in the tree. Consider the example `root = [1,null,2,3]`. For the root node `1`, we first process its left subtree (which is empty). Then, we add `1` to our result. Next, we move to its right subtree, rooted at `2`. Now, applying the inorder rule to `2`: its left child is `3`. So we process `3`'s left subtree (empty), then add `3` to the result, then process `3`'s right subtree (empty). After `3` is fully traversed, we return to `2`, add `2` to the result, and finally process `2`'s right subtree (empty). The final sequence is `[1,3,2]`. This specific traversal is particularly important because, for a Binary Search Tree, it conveniently yields the node values in sorted order.

Solution Approach

The provided solution implements an iterative Depth-First Search (DFS) for inorder traversal, cleverly circumventing explicit recursion by using an auxiliary stack. The core idea is to simulate the recursive call stack: we continuously descend down the left child path, pushing each visited node onto the stack. These stacked nodes represent ancestors whose left subtrees we're currently exploring, and whose values we haven't yet 'processed'. When we finally hit a `null` node (meaning we've gone as far left as possible in the current subtree), we know the leftmost node's left subtree is fully explored. It's then time to pop a node from the stack. This popped node is the 'current root' that we need to process (add its value to our result). Crucially, after processing this node, we immediately set `curr` to its *right* child. This ensures that the next iteration of the outer `while` loop will either continue descending left from this new `curr` (if it's not null), or, if it's null, we'll pop the next pending ancestor from the stack to process its value and then explore its right subtree. This loop continues until both `curr` is null and the stack is empty, meaning all nodes have been visited.

Step-by-Step Algorithm

Step 1: Initialize an empty list `res` to store the inorder traversal result and an empty stack `stack`.
Step 2: Initialize `curr` to the root node.
Step 3: While `curr` is not null or the `stack` is not empty:
Step 4: While `curr` is not null, push `curr` onto the `stack` and move `curr` to its left child (`curr.left`).
Step 5: Pop the top node from the `stack` and assign it to `curr`.
Step 6: Add `curr.val` to the `res` list.
Step 7: Move `curr` to its right child (`curr.right`).
Step 8: Return `res`.

Key Insights

An iterative Depth-First Search (DFS) for inorder traversal meticulously simulates the recursive call stack by using an explicit stack to store nodes whose left subtrees are yet to be fully explored. This allows us to defer processing a node's value until its entire left subtree has been visited.
The pattern of `while curr: stack.append(curr); curr = curr.left` is paramount. It ensures that we always push nodes onto the stack as we dive deep into the leftmost branch. The stack then acts as a 'breadcrumb trail' of parent nodes waiting for their left children to be fully processed.
The specific sequence of `curr = stack.pop(); res.append(curr.val); curr = curr.right` perfectly encapsulates the 'root-then-right' part of the inorder traversal. After popping and processing a node, we *must* immediately pivot to its right child to maintain the correct inorder sequence for that branch, repeating the 'descend-left' process from this new starting point.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Stack, Tree, Depth-First Search, Binary Tree.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Meta, Microsoft, Uber.

Binary Tree Inorder Traversal | LeetCode 94

Easy

Stack Tree Depth-First Search Binary Tree

Time: O(n)Space: O(n)

Solution Code

Available in:

/**
 * 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<>();
        Stack<TreeNode> stack = new Stack<>();
        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;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 94: Binary Tree Inorder Traversal - Detailed explanation and solution approaches.

Topics

Stack Tree Depth-First Search Binary Tree

Companies

AdobeAmazonAppleBloombergMetaMicrosoftUber

Stats

Difficulty:Easy

Languages:4

Companies:7

Problem #:94

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize an empty list `res` to store the inorder traversal result and an empty stack `stack`.
2
Step 2: Initialize `curr` to the root node.
3
Step 3: While `curr` is not null or the `stack` is not empty:
4
Step 4: While `curr` is not null, push `curr` onto the `stack` and move `curr` to its left child (`curr.left`).
5
Step 5: Pop the top node from the `stack` and assign it to `curr`.
6
Step 6: Add `curr.val` to the `res` list.
7
Step 7: Move `curr` to its right child (`curr.right`).
8
Step 8: Return `res`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The algorithm visits each node in the tree exactly once, resulting in a time complexity of O(n), where n is the number of nodes. The space complexity is determined by the maximum height (h) of the tree, as the stack can store at most h nodes in the worst-case scenario (a skewed tree). In the case of a balanced tree, h = log₂(n), resulting in O(log n) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach

A recursive function visits the left subtree, then the root, then the right subtree. This is a more concise but potentially less efficient solution for very deep trees due to function call overhead.

Time: O(n)Space: O(h)

Trade-offs: Recursive is simpler to understand and write but may suffer from stack overflow errors for extremely deep trees. Iterative is generally preferred for its efficiency and avoidance of potential stack overflow.

✨

Key Insights

1An iterative Depth-First Search (DFS) for inorder traversal meticulously simulates the recursive call stack by using an explicit stack to store nodes whose left subtrees are yet to be fully explored. This allows us to defer processing a node's value until its entire left subtree has been visited.
2The pattern of `while curr: stack.append(curr); curr = curr.left` is paramount. It ensures that we always push nodes onto the stack as we dive deep into the leftmost branch. The stack then acts as a 'breadcrumb trail' of parent nodes waiting for their left children to be fully processed.
3The specific sequence of `curr = stack.pop(); res.append(curr.val); curr = curr.right` perfectly encapsulates the 'root-then-right' part of the inorder traversal. After popping and processing a node, we *must* immediately pivot to its right child to maintain the correct inorder sequence for that branch, repeating the 'descend-left' process from this new starting point.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root is null). The while loop condition handles this correctly; the loop terminates immediately, returning an empty list.
Edge case 2: Single-node tree. The algorithm correctly processes the single node and returns a list containing its value.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly handling the stack operations. Pushing and popping nodes from the stack in the wrong order will lead to an incorrect traversal.

✗Common mistake 2: Forgetting to handle the empty tree case. The code must gracefully handle a null root to avoid null pointer exceptions or segmentation faults.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Processing hierarchical data structures. Inorder traversal is useful when you need to process data in a sorted order, such as displaying a sorted list of items from a hierarchical database.

🏦Real-world scenario 2: Expression evaluation in compilers. Inorder traversal can be used to represent and evaluate arithmetic expressions stored in a binary tree format.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Stacks are perfect for problems involving matching (parentheses) or "next greater element" patterns. If you need to look back at recent elements, think stack.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Popping from an empty stack. Always check if the stack is non-empty before popping.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Binary Tree Inorder Traversal"?

For this easy-level Stack problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether tree techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?