Skip to main content
Talentd

Binary Tree Inorder Traversal - Solution & Explanation

EasyStackTreeDepth-First SearchBinary Tree31 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

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?

Approach Overview

Problem Overview: Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder means you always visit the left subtree, then the current node, then the right subtree.

Approach 1: Recursive Inorder Traversal (O(n) time, O(h) space)

This approach uses recursion to follow the natural definition of inorder traversal. Starting from the root, recursively traverse the left child, append the current node value to the result array, then recursively traverse the right child. The recursion stack implicitly handles the traversal order. Each node is visited exactly once, giving O(n) time complexity. The space complexity is O(h), where h is the height of the tree, due to the recursion call stack. This method is the cleanest and easiest to implement when working with tree traversal problems.

Approach 2: Iterative Inorder Traversal Using Stack (O(n) time, O(h) space)

This method simulates recursion using an explicit stack. Start from the root and repeatedly push nodes while moving to the leftmost child. When no more left children exist, pop the top node from the stack, record its value, and move to its right child. Repeat the process until both the stack is empty and the current node is null. Each node is pushed and popped at most once, so the traversal runs in O(n) time. The stack holds at most the height of the tree, giving O(h) space. This technique is common in iterative depth-first search implementations.

Recommended for interviews: Interviewers expect you to know both approaches. The recursive version shows you understand tree traversal fundamentals and DFS ordering. The iterative stack solution demonstrates stronger control over execution flow and the ability to convert recursion into an explicit data structure. Many interviewers ask for the iterative version after seeing the recursive solution.

Approach 1: Recursive Inorder Traversal

This approach uses recursion to traverse the binary tree. Inorder traversal involves visiting the left subtree, the root node, and then the right subtree. The base case for the recursion is to return if the current node is null.

The C solution defines a helper function inorderTraversalHelper to perform the recursion. The function is called with the current node and a result array to store the values. This implementation assumes a maximum of 100 nodes and allocates space accordingly, which is suitable for the problem constraints but would require dynamic reallocation in a more general scenario.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree.

Space Complexity: O(n) due to the recursion stack.

Try this approach in the editor →

Approach 2: Iterative Inorder Traversal

In this approach, we use a stack to perform an iterative inorder traversal. The stack is utilized to track the nodes to be visited. This method mimics the recursive behavior by explicitly using a stack to push left children until reaching a null entry, then processes the nodes and explores the right subtrees.

The C implementation employs a manual stack data structure to facilitate the iterative traversal. Nodes are pushed onto the stack until null is reached, allowing us to backtrack, visit the node, and repeat the process for the right subtree.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)

Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Recursive Traversal

We first recursively traverse the left subtree, then visit the root node, and finally recursively traverse the right subtree.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree, and the space complexity mainly depends on the stack space of the recursive call.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Stack Implementation for Non-recursive Traversal

The non-recursive approach is as follows:

  1. Define a stack stk.
  2. Push the left nodes of the tree into the stack in sequence.
  3. When the left node is null, pop and process the top element of the stack.
  4. Repeat steps 2-3.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree, and the space complexity mainly depends on the stack space.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 5: Morris Implementation for In-order Traversal

Morris traversal does not require a stack, so the space complexity is O(1). The core idea is:

Traverse the binary tree nodes,

  1. If the left subtree of the current node root is null, add the current node value to the result list ans, and update the current node to root.right.
  2. If the left subtree of the current node root is not null, find the rightmost node prev of the left subtree (which is the predecessor node of the root node in in-order traversal):
    • If the right subtree of the predecessor node prev is null, point the right subtree of the predecessor node to the current node root, and update the current node to root.left.
    • If the right subtree of the predecessor node prev is not null, add the current node value to the result list ans, then point the right subtree of the predecessor node to null (i.e., disconnect prev and root), and update the current node to root.right.
  3. Repeat the above steps until the binary tree node is null, and the traversal ends.

The time complexity is O(n), and the space complexity is O(1). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Inorder Traversal

Time Complexity: O(n), where n is the number of nodes in the binary tree.

Space Complexity: O(n) due to the recursion stack.

Iterative Inorder Traversal

Time Complexity: O(n)

Space Complexity: O(n)

Recursive Traversal—
Stack Implementation for Non-recursive Traversal—
Morris Implementation for In-order Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Inorder TraversalO(n)O(h)Best for readability and quick implementation when recursion is allowed
Iterative Traversal with StackO(n)O(h)Preferred when avoiding recursion or when interviewers ask for iterative DFS

Video Solution

Iterative & Recursive - Binary Tree Inorder Traversal - Leetcode 94 - Python • NeetCode • 158,573 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Tree Inorder Traversal easy or hard?
Binary Tree Inorder Traversal is considered an easy problem because it focuses on a fundamental DFS traversal pattern. However, it forms the foundation for many medium and hard tree problems, making it essential to master early.
How to solve Binary Tree Inorder Traversal in O(n)?
Traverse the tree using depth‑first search while maintaining the inorder order: left subtree, current node, then right subtree. Either use recursion to naturally follow this order or simulate it iteratively with a stack that tracks nodes while moving left through the tree.
Binary Tree Inorder Traversal Python or Java solution?
Python and Java implementations both follow the same logic: recursively visit the left child, record the node value, then visit the right child. Iterative solutions use a stack to push nodes while traversing left, then pop nodes to process them and move to the right subtree.
What is the best approach for Binary Tree Inorder Traversal?
Both recursive DFS and iterative stack traversal are optimal for this problem. Each visits every node exactly once, giving O(n) time complexity. The recursive solution is shorter and easier to write, while the iterative stack approach demonstrates deeper understanding of traversal mechanics and is often preferred in interviews.
Is Binary Tree Inorder Traversal asked at Google/Amazon/Meta?
Binary tree traversal problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often build on this concept, such as validating a BST, recovering a BST, or converting a tree to a sorted sequence using inorder traversal.
What data structure is used in Binary Tree Inorder Traversal?
The recursive approach relies on the call stack, while the iterative approach explicitly uses a stack data structure. The stack keeps track of nodes whose right subtrees still need to be visited after finishing their left subtree.
What is the time complexity of Binary Tree Inorder Traversal?
Binary Tree Inorder Traversal runs in O(n) time because every node in the tree is visited exactly once. Whether using recursion or an explicit stack, each node is processed a single time during the traversal.

Ready to solve this problem?

Practice Binary Tree Inorder Traversal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Search Tree Iterator

Next

Binary Tree Postorder Traversal