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 <= 100The goal of inorder traversal in a binary tree is to visit nodes in the order: Left → Root → Right. This traversal naturally produces sorted output when applied to a Binary Search Tree (BST). Understanding this visiting order is the key idea behind solving the problem.
A common approach is using Depth-First Search (DFS) recursion. The algorithm recursively explores the left subtree, processes the current node, and then traverses the right subtree. This mirrors the definition of inorder traversal and keeps the implementation clean and intuitive.
Another popular approach is the iterative method using a stack. Instead of recursion, a stack is used to simulate the function call stack. You repeatedly push nodes while moving left, process the node when no further left child exists, and then move to the right subtree.
Both approaches visit each node exactly once, giving a time complexity of O(n). The space complexity depends on the recursion depth or stack size, which in the worst case can reach O(n) for highly skewed trees.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive DFS | O(n) | O(h) (up to O(n) in worst case) |
| Iterative Stack | O(n) | O(h) (up to O(n) in worst case) |
NeetCode
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.
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n) due to the recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode
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.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, inorder traversal is a fundamental tree problem frequently asked in FAANG and other top tech company interviews. It often appears as a base concept for more complex problems involving binary trees or binary search trees.
A stack is the most useful data structure for implementing the iterative inorder traversal. It helps simulate the recursive call stack while exploring the left subtree before visiting nodes. In recursive solutions, the program’s call stack performs this role automatically.
The optimal approach is typically a recursive Depth-First Search that processes nodes in the order Left, Root, Right. It is simple to implement and naturally follows the definition of inorder traversal. An iterative stack-based approach is also commonly used in interviews.
Recursive inorder traversal uses function calls to explore the left subtree, process the node, and then visit the right subtree. Iterative traversal replaces recursion with an explicit stack, giving more control over execution and avoiding deep recursion limits.
JavaScript utilizes arrays as stacks to perform an iterative traversal of the binary tree. The result array is sequentially filled following the inorder sequence starting from the traversal's leftmost node.