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:
[0, 100].-100 <= Node.val <= 100Follow up: Recursive solution is trivial, could you do it iteratively?
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.
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.
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n) due to the recursion stack.
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.
Time Complexity: O(n)
Space Complexity: O(n)
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
The non-recursive approach is as follows:
stk.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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Morris traversal does not require a stack, so the space complexity is O(1). The core idea is:
Traverse the binary tree nodes,
root is null, add the current node value to the result list ans, and update the current node to root.right.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):prev is null, point the right subtree of the predecessor node to the current node root, and update the current node to root.left.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.The time complexity is O(n), and the space complexity is O(1). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Inorder Traversal | O(n) | O(h) | Best for readability and quick implementation when recursion is allowed |
| Iterative Traversal with Stack | O(n) | O(h) | Preferred when avoiding recursion or when interviewers ask for iterative DFS |
Iterative & Recursive - Binary Tree Inorder Traversal - Leetcode 94 - Python • NeetCode • 151,613 views views
Watch 9 more video solutions →Practice Binary Tree Inorder Traversal with our built-in code editor and test cases.
Practice on FleetCode