Binary Tree Inorder Traversal
Description
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Inorder traversal follows the pattern: Left subtree → Root → Right subtree. For every node in the tree, you first visit all nodes in its left subtree, then record the current node's value, and finally visit all nodes in its right subtree.
This traversal order is particularly significant because when applied to a Binary Search Tree (BST), it produces the node values in sorted (ascending) order.
Examples
Example 1
Input: root = [1, null, 2, 3]
The tree looks like:
1
\
2
/
3
Output: [1, 3, 2]
Explanation: Starting from the root (1), we first check its left subtree — it has no left child, so we record 1. Then we move to the right child (2). Node 2 has a left child (3), so we visit 3 first (it has no children, record 3), then record 2. The final traversal order is [1, 3, 2].
Example 2
Input: root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]
The tree looks like:
1
/ \
2 3
/ \ \
4 5 8
/ \ /
6 7 9
Output: [4, 2, 6, 5, 7, 1, 3, 9, 8]
Explanation: Following the Left-Root-Right pattern recursively: we go deep left to 4 (no children, record 4), back to 2 (record 2), then into 2's right subtree rooted at 5 — visit 6 (record 6), then 5 (record 5), then 7 (record 7). Back to root 1 (record 1). Then right subtree: 3 has no left child (record 3), then into 8's left child 9 (record 9), then 8 (record 8). Result: [4, 2, 6, 5, 7, 1, 3, 9, 8].
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no nodes to visit, so the result is an empty list.
Example 4
Input: root = [1]
Output: [1]
Explanation: A single-node tree has no left or right subtree. We simply record the root's value.
Constraints
- The number of nodes in the tree is in the range [0, 100]
- -100 ≤ Node.val ≤ 100
Editorial
Brute Force
Intuition
The most natural way to perform an inorder traversal is to follow the definition directly using recursion. The rule is simple: for any node, first process everything on its left, then process the node itself, then process everything on its right.
Think of it like reading a family tree from the bottom-left upward. You always want to read the leftmost descendant first, then its parent, then its right sibling's descendants. Recursion handles all the bookkeeping of remembering where to return after finishing a subtree — the call stack keeps track of pending nodes automatically.
This approach is straightforward and mirrors the mathematical definition of inorder traversal, making it the natural starting point.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, null, 2, 3]
Tree structure:
1
\
2
/
3
Step 1: Call inorder(node=1). Node 1 exists, so first recurse into the left subtree.
Step 2: Call inorder(node=null). Left child of 1 is null, so return immediately. Nothing to process.
Step 3: Back at node 1. Left subtree is done. Record node 1's value → result = [1].
Step 4: Now recurse into node 1's right subtree. Call inorder(node=2).
Step 5: Node 2 exists. First recurse into its left subtree. Call inorder(node=3).
Step 6: Node 3 exists. First recurse into its left subtree. Call inorder(node=null). Left child of 3 is null, return immediately.
Step 7: Back at node 3. Left subtree done. Record node 3's value → result = [1, 3].
Step 8: Recurse into node 3's right subtree. Call inorder(node=null). Right child of 3 is null, return immediately.
Step 9: Back at node 2. Left subtree (rooted at 3) is fully processed. Record node 2's value → result = [1, 3, 2].
Step 10: Recurse into node 2's right subtree. Call inorder(node=null). Right child of 2 is null, return immediately.
Step 11: All calls complete. Final result = [1, 3, 2].
Recursive Inorder Traversal of [1, null, 2, 3] — Watch how recursion dives to the leftmost node first, records values in Left-Root-Right order, and the call stack automatically manages backtracking.
Algorithm
- If the current node is null, return (base case)
- Recursively call inorder on the left child
- Record the current node's value into the result list
- Recursively call inorder on the right child
- Return the result list
Code
/**
* 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 {
public:
void helper(TreeNode* node, vector<int>& result) {
if (node == nullptr) return;
helper(node->left, result);
result.push_back(node->val);
helper(node->right, result);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
helper(root, result);
return result;
}
};# 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 helper(node):
if node is None:
return
helper(node.left)
result.append(node.val)
helper(node.right)
helper(root)
return result/**
* 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<>();
helper(root, result);
return result;
}
private void helper(TreeNode node, List<Integer> result) {
if (node == null) return;
helper(node.left, result);
result.add(node.val);
helper(node.right, result);
}
}Complexity Analysis
Time Complexity: O(n)
Every node in the tree is visited exactly once. At each node, we do constant work (one comparison, one append). With n nodes total, the time complexity is O(n).
Space Complexity: O(n)
The space is consumed by the recursion call stack. In the worst case (a completely skewed tree where every node has only a left or only a right child), the recursion depth equals n, leading to O(n) stack space. In the best case (a balanced tree), the depth is O(log n). Additionally, the result list takes O(n) space, but since that's required for the output, the auxiliary space overhead is dominated by the call stack: O(n) worst case.
Why This Approach Is Not Efficient
The recursive approach works correctly and runs in O(n) time, which is optimal for visiting every node. However, it uses O(n) auxiliary space in the worst case due to the implicit recursion call stack.
For a skewed tree with 100 nodes (the maximum per constraints), recursion would create 100 nested function calls. While this is manageable for small inputs, in production systems with much larger trees, deep recursion can cause stack overflow errors. Each recursive call consumes stack memory for local variables, return addresses, and function metadata.
The key question is: can we achieve the same traversal without relying on the system's call stack? The answer is yes — we can manage our own stack explicitly, which gives us more control over memory usage. This leads us to the iterative approach.
Better Approach - Iterative with Stack
Intuition
The recursive approach uses the system's call stack to remember which nodes to return to after finishing a subtree. We can replicate this exact behavior using an explicit stack data structure.
The core idea: in inorder traversal, we always want to go as far left as possible first. So we keep pushing nodes onto the stack as we move left. When we can't go left anymore (hit a null), we pop the top node from the stack — that's the next node in inorder sequence. After recording it, we move to its right child and repeat the process.
Think of it like exploring a cave system. You always take the leftmost tunnel first. You leave breadcrumbs (push to stack) at each fork. When you hit a dead end (null), you backtrack to the last breadcrumb (pop from stack), mark that spot as explored, and then take the right tunnel from there.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, null, 2, 3]
Tree:
1
\
2
/
3
Step 1: Initialize: stack = [], current = node(1), result = []. Start by going as far left as possible from the root.
Step 2: current = node(1). Push 1 onto stack. Move left. stack = [1], current = null.
Step 3: current is null. Can't go left anymore. Pop from stack: node 1. Record value 1. result = [1]. Move to node 1's right child: current = node(2).
Step 4: current = node(2). Push 2 onto stack. Move left. stack = [2], current = node(3).
Step 5: current = node(3). Push 3 onto stack. Move left. stack = [2, 3], current = null.
Step 6: current is null. Pop from stack: node 3. Record value 3. result = [1, 3]. Move to node 3's right child: current = null.
Step 7: current is null. Pop from stack: node 2. Record value 2. result = [1, 3, 2]. Move to node 2's right child: current = null.
Step 8: current is null and stack is empty. Loop ends. Final result = [1, 3, 2].
Iterative Inorder Traversal with Explicit Stack — Watch how the explicit stack replaces recursion — we push nodes while going left, pop to visit, then move right.
Algorithm
- Initialize an empty stack and set current = root
- While current is not null OR stack is not empty:
a. While current is not null: push current onto stack, move current = current.left
b. Pop the top node from stack
c. Record the popped node's value
d. Set current = popped node's right child - Return the result list
Code
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* current = root;
while (current != nullptr || !stk.empty()) {
// Go as far left as possible
while (current != nullptr) {
stk.push(current);
current = current->left;
}
// Pop the top node
current = stk.top();
stk.pop();
// Record the value
result.push_back(current->val);
// Move to right subtree
current = current->right;
}
return result;
}
};class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
stack = []
current = root
while current is not None or stack:
# Go as far left as possible
while current is not None:
stack.append(current)
current = current.left
# Pop the top node
current = stack.pop()
# Record the value
result.append(current.val)
# Move to right subtree
current = current.right
return resultclass Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// Go as far left as possible
while (current != null) {
stack.push(current);
current = current.left;
}
// Pop the top node
current = stack.pop();
// Record the value
result.add(current.val);
// Move to right subtree
current = current.right;
}
return result;
}
}Complexity Analysis
Time Complexity: O(n)
Each node is pushed onto the stack exactly once and popped exactly once. The inner while loop (going left) across all outer iterations processes each node at most once. Therefore, the total work is O(n).
Space Complexity: O(n)
The explicit stack stores nodes along the current path from the root to the leftmost unvisited node. In the worst case (a left-skewed tree), all n nodes are pushed onto the stack before any pop occurs, giving O(n) space. For a balanced tree, the maximum stack depth is O(log n). The result list also takes O(n) space.
Why This Approach Is Not Efficient
The iterative stack-based approach gives us explicit control over the stack, avoiding potential stack overflow from deep recursion. However, it still uses O(n) auxiliary space in the worst case for the stack itself.
Both the recursive and iterative-stack approaches share the same fundamental limitation: they need extra storage proportional to the tree height (and up to n in the worst case) to remember which nodes to revisit.
The question becomes: can we traverse the tree in inorder without using ANY extra space beyond the output list? This seems impossible because once we go left, we lose our way back to the parent. But there's a clever trick: we can temporarily modify the tree structure to create 'breadcrumb' links back to parent nodes, then restore the tree after using them. This is the idea behind Morris Traversal.
Optimal Approach - Morris Traversal
Intuition
Morris Traversal is a brilliant technique that achieves inorder traversal using O(1) extra space by temporarily modifying the tree's structure. The key insight is that in the inorder sequence, the inorder predecessor of any node is the rightmost node in its left subtree. After visiting that predecessor, the next node in sequence is the current node itself.
Morris Traversal exploits this relationship: before going into a node's left subtree, it creates a temporary link from the inorder predecessor back to the current node. This link serves as a 'return path' — when we finish the left subtree and reach the predecessor, the temporary link guides us back to the current node without needing a stack.
Think of it like leaving a trail of thread in a maze. Before entering a left corridor, you tie a thread from the dead end of that corridor back to the junction you came from. When you reach that dead end, the thread guides you back. After returning, you cut the thread to restore the maze to its original state.
The algorithm processes each node by asking two questions:
- Does this node have a left child?
- If yes, has its left subtree already been visited (is there already a temporary link)?
If there's no left child, the node is next in inorder — record it and go right. If there IS a left child but no temporary link yet, create the link and go left. If the temporary link already exists, the left subtree is fully processed — remove the link, record the current node, and go right.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, null, 2, 3]
Tree:
1
\
2
/
3
Step 1: Set current = node(1). Check: does node 1 have a left child? No. Since there's no left subtree, node 1 is the next node in inorder. Record 1. result = [1]. Move right: current = node(2).
Step 2: current = node(2). Check: does node 2 have a left child? Yes (node 3). Find the inorder predecessor of node 2: go to left child (3), then go as far right as possible. Node 3 has no right child, so node 3 itself is the predecessor.
Step 3: Does predecessor (node 3) already point back to current (node 2)? No (its right is null). Create temporary link: set node 3's right = node 2. Now move left: current = node(3).
Step 4: current = node(3). Check: does node 3 have a left child? No. Record 3. result = [1, 3]. Move right. But wait — node 3's right was set to node 2 in the previous step (the temporary link)! So current = node(2).
Step 5: current = node(2) again. Check: does node 2 have a left child? Yes (node 3). Find predecessor: go left to 3, go right... node 3's right points to node 2 (it's the temporary link). Since predecessor's right == current, the left subtree has been fully visited.
Step 6: Remove the temporary link: set node 3's right = null (restore original tree). Record node 2. result = [1, 3, 2]. Move right: current = node(2).right = null.
Step 7: current = null. Loop ends. Final result = [1, 3, 2].
Morris Inorder Traversal — O(1) Space with Temporary Links — Watch how Morris Traversal creates and removes temporary thread links to navigate the tree without a stack, achieving O(1) auxiliary space.
Algorithm
- Set current = root
- While current is not null:
a. If current has no left child:- Record current's value
- Move to current's right child
b. If current has a left child: - Find the inorder predecessor (rightmost node in left subtree)
- If predecessor's right is null (first visit):
- Set predecessor's right = current (create temporary link)
- Move current to its left child
- If predecessor's right == current (second visit):
- Set predecessor's right = null (remove temporary link, restore tree)
- Record current's value
- Move current to its right child
- Return the result list
Code
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
TreeNode* current = root;
while (current != nullptr) {
if (current->left == nullptr) {
// No left subtree: visit current, go right
result.push_back(current->val);
current = current->right;
} else {
// Find inorder predecessor
TreeNode* predecessor = current->left;
while (predecessor->right != nullptr && predecessor->right != current) {
predecessor = predecessor->right;
}
if (predecessor->right == nullptr) {
// First visit: create thread, go left
predecessor->right = current;
current = current->left;
} else {
// Second visit: remove thread, visit current, go right
predecessor->right = nullptr;
result.push_back(current->val);
current = current->right;
}
}
}
return result;
}
};class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
current = root
while current is not None:
if current.left is None:
# No left subtree: visit current, go right
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
predecessor = current.left
while predecessor.right is not None and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
# First visit: create thread, go left
predecessor.right = current
current = current.left
else:
# Second visit: remove thread, visit current, go right
predecessor.right = None
result.append(current.val)
current = current.right
return resultclass Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// No left subtree: visit current, go right
result.add(current.val);
current = current.right;
} else {
// Find inorder predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// First visit: create thread, go left
predecessor.right = current;
current = current.left;
} else {
// Second visit: remove thread, visit current, go right
predecessor.right = null;
result.add(current.val);
current = current.right;
}
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(n)
Although finding the predecessor for each node appears to add extra work, every edge in the tree is traversed at most three times total (once going down, once creating the thread, once removing the thread). The amortized cost per node is O(1), giving O(n) total.
A more precise analysis: each edge is visited at most twice during predecessor finding across ALL iterations, and there are n-1 edges in a tree with n nodes. So the total extra work from predecessor finding is O(n), and the main loop runs O(n) times. Total: O(n) + O(n) = O(n).
Space Complexity: O(1)
Morris Traversal uses only two pointer variables (current and predecessor) regardless of tree size. No stack, no recursion. The tree is temporarily modified but restored to its original structure by the end. The result list takes O(n) but is required for the output — the auxiliary space is genuinely O(1).
This makes Morris Traversal the space-optimal approach for inorder traversal.