Binary Tree Inorder Traversal (LeetCode 94)
A binary tree is given by its root. Return the values of its nodes in inorder. Inorder lists, for every node, the values of its left subtree first, then the value of the node itself, then the values of its right subtree.
The tree is not necessarily a search tree: values can repeat and can come in any order.
Follow-up: the recursive walk is short. Can you write the walk with a stack of your own instead?
Worked Examples
root = [1,null,2,3][1,3,2]root = [1,2,3,4,5,null,8,null,null,6,7,9][4,2,6,5,7,1,3,9,8]root = [][]root = [1][1]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
Core Insight
A depth-first walk reaches every node three times: on the way down, after its left subtree and after its right subtree. Inorder lists the node at the second time, which is when stack.pop() hands the node back, so result.append(node.val) goes right after the pop.
Real-World Scenario & Production Applications
Programs that print or export a tree must choose an order. A file manager lists a folder before the files inside it, which is preorder. A search tree that a database keeps for an index is read in sorted order, which is inorder. A program that deletes a folder must remove the files inside it first, which is postorder. All three orders are the same walk, with the visit placed at a different moment.
Step-by-Step Execution Trace Table
Example 1, root = [1,null,2,3]. The columns show the state after each row:
| Step | What runs | stack (bottom to top) | node | result | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [1] | None | [] | 1 is pushed, not visited: its left subtree comes first |
| 2 | node = stack.pop(), result.append(node.val), node = node.right | [] | 2 | [1] | 1 has no left subtree, so it is visited now; the walk goes right |
| 3 | Dive: push 2, then push 3 | [2, 3] | None | [1] | 3 is the left child of 2, so 2 must wait |
| 4 | Pop 3, append, node = node.right | [2] | None | [1, 3] | 3 is visited before 2 |
| 5 | Pop 2, append, node = node.right | [] | None | [1, 3, 2] | node is None and stack is empty, so the loop ends |
Appending when a node is pushed would add 1, then 2, then 3, and return the preorder [1, 2, 3].
root = [1,null,2,3][1,3,2]Example 1, root = [1,null,2,3]. The columns show the state after each row:
| Step | What runs | stack (bottom to top) | node | result | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [1] | None | [] | 1 is pushed, not visited: its left subtree comes first |
| 2 | node = stack.pop(), result.append(node.val), node = node.right | [] | 2 | [1] | 1 has no left subtree, so it is visited now; the walk goes right |
| 3 | Dive: push 2, then push 3 | [2, 3] | None | [1] | 3 is the left child of 2, so 2 must wait |
| 4 | Pop 3, append, node = node.right | [2] | None | [1, 3] | 3 is visited before 2 |
| 5 | Pop 2, append, node = node.right | [] | None | [1, 3, 2] | node is None and stack is empty, so the loop ends |
Appending when a node is pushed would add 1, then 2, then 3, and return the preorder [1, 2, 3].
| 1 | A depth-first walk reaches each node three times: on the way down, after its left subtree, and after its right subtree. The order name says which time lists the node. |
| 2 | Keep `stack` and `node = root`, and loop `while node or stack`: an inner `while node` pushes and moves to `node.left`, then pop, append `node.val` and move to `node.right`. |
| 3 | Preorder appends at the push, inorder at the pop, and postorder only when `top.right` is empty or `top.right is last`. |
| 4 | The trap: append after the pop in inorder. Appending at the push returns the preorder, `[1, 2, 3]` instead of `[1, 3, 2]` on `[1,null,2,3]`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A tree has no first, second and third element, so a list of its nodes needs a rule for the order. A depth-first walk reaches every node three times: on the way down, when it comes back from the left subtree, and when it comes back from the right subtree. The three visit orders differ only in which of those times adds the node to the list. Preorder lists the node on the way down, inorder after its left subtree, and postorder after its right subtree.
📚 The Analogy: A Folder Tree
A folder holds files and other folders. To copy the tree you create each folder before the things inside it: that is preorder. To delete the tree you remove the things inside a folder before the folder itself, because a folder with contents cannot be removed: that is postorder. Inorder needs two children, so it fits a binary tree: the node comes between its left and right subtrees. In a binary search tree that is exactly sorted order.
🔑 Why It Works
Recursion keeps the nodes that are waiting for the walk to come back in the call stack. An explicit stack keeps the same nodes in a list that you control. The inner loop pushes every node on the way down the left edge, so the node that stack.pop() returns has a finished left subtree. Appending its value right after the pop lists it between its two subtrees, and node = node.right starts the right subtree. Each node is pushed once and popped once.
Appending
node.valwhennodeis pushedLooping
while stackinstead ofwhile node or stackPopping a node in postorder without checking
top.right is not lastComparing
top.right.valwithlast.valinstead of the nodesWalking a deep tree with recursion
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Return the inorder traversal of its nodes' values" names an order, and the follow-up asks for the walk without recursion. A list of the nodes in a named visit order is Tree Traversals: one walk, with the visit placed at the moment the order name says.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before each stack.pop(), every value in result comes before every node still on stack, in inorder. The popped node has a finished left subtree, so result.append(node.val) adds the next value, and node = node.right starts the right subtree.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
result.append(node.val)goes afterstack.pop(), never next tostack.append(node). At the push, the list is the preorder,[1, 2, 3]instead of[1, 3, 2]on[1,null,2,3].while node or stack, neverwhile stack:stackis empty at the start, sowhile stackreturns[].root = []givesnode = Noneand an emptystack, so the loop never runs andresultis[]. Code that readsroot.valfirst fails on this input.The recursion is safe here, because the tree has at most 100 nodes. A chain of 3000 nodes raises RecursionError, which is why the explicit
stackis the form to know.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Tree Traversals on an explicit stack. Inorder means left subtree, then the node, then the right subtree. I keep a stack of the nodes whose left subtree is still being walked. From a node, I push it and move to its left child, again and again, until there is no left child. Then I pop one node. Its left subtree is finished, so I append its value to the result. Then I move to its right child, and the same dive starts again. The loop runs while there is a current node or the stack is not empty, because the stack can be empty while a right subtree is still waiting. The trap is where I append: after the pop, never at the push, or I would return the preorder. Each node is pushed once and popped once, so the time is order N, and the stack holds at most the height of the tree, so the space is order H.
Complexity & Mathematical Proof
O(N)
Look at the code: the inner while node: loop pushes one node per pass, and the outer loop pops one node per pass. A node is pushed when the walk first reaches it, and it is popped once, after its left subtree. Nothing pushes a node a second time, because node = node.right moves to a node that has never been pushed. So the walk makes N pushes and N pops, and each push, pop and append is O(1). Total: O(N).
O(H) stack
Every node on stack is an ancestor of node whose left subtree is still being walked, so stack holds at most one root-to-leaf path: O(H) nodes, where H is the height of the tree. The returned list holds N values; it is the output and is not counted.
Derivation Progression
N pushes
stack.append(node) runs once for each node, when the dive reaches it.
N pops and N appends
Each pass of while node or stack: pops one node and appends its value; the loop ends when every node has been popped.
N assignments
node = node.right runs once per pop and moves to a subtree that has not been pushed yet.
O(N)
Each push, pop, append and assignment is O(1).
Variable Definitions
Number of nodes in the tree (0 to 100 here)
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(1): iterative, no recursion
O(H): stack holds one root-to-leaf path at most
O(N): the returned list (not counted)
Boundary Best / Worst Cases
: every node is visited, whatever the shape
time and stack on a balanced tree
time; the stack grows to on a chain that leans left
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "inorder traversal", "could you do it iteratively?". A named visit order plus a request to avoid recursion: Tree Traversals with an explicit stack.
nodes and values in . One walk is time, and stack holds one root-to-node path, , which is at most 100 here, so recursion would also work. Binary Search Tree Iterator (LC 173) allows nodes in one chain, which passes Python's default recursion limit of 1000.
Appending node.val at the push returns the preorder, and while stack never starts. A walk that is paused between calls, such as an iterator, must keep stack and node as fields of an object, because local variables are lost when the function returns.
Binary Tree Inorder Traversal (LeetCode 94)
A binary tree is given by its root. Return the values of its nodes in inorder. Inorder lists, for every node, the values of its left subtree first, then the value of the node itself, then the values of its right subtree.
The tree is not necessarily a search tree: values can repeat and can come in any order.
Follow-up: the recursive walk is short. Can you write the walk with a stack of your own instead?
Worked Examples
root = [1,null,2,3][1,3,2]root = [1,2,3,4,5,null,8,null,null,6,7,9][4,2,6,5,7,1,3,9,8]root = [][]root = [1][1]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
Core Insight
A depth-first walk reaches every node three times: on the way down, after its left subtree and after its right subtree. Inorder lists the node at the second time, which is when stack.pop() hands the node back, so result.append(node.val) goes right after the pop.
Real-World Scenario & Production Applications
Programs that print or export a tree must choose an order. A file manager lists a folder before the files inside it, which is preorder. A search tree that a database keeps for an index is read in sorted order, which is inorder. A program that deletes a folder must remove the files inside it first, which is postorder. All three orders are the same walk, with the visit placed at a different moment.
Step-by-Step Execution Trace Table
Example 1, root = [1,null,2,3]. The columns show the state after each row:
| Step | What runs | stack (bottom to top) | node | result | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [1] | None | [] | 1 is pushed, not visited: its left subtree comes first |
| 2 | node = stack.pop(), result.append(node.val), node = node.right | [] | 2 | [1] | 1 has no left subtree, so it is visited now; the walk goes right |
| 3 | Dive: push 2, then push 3 | [2, 3] | None | [1] | 3 is the left child of 2, so 2 must wait |
| 4 | Pop 3, append, node = node.right | [2] | None | [1, 3] | 3 is visited before 2 |
| 5 | Pop 2, append, node = node.right | [] | None | [1, 3, 2] | node is None and stack is empty, so the loop ends |
Appending when a node is pushed would add 1, then 2, then 3, and return the preorder [1, 2, 3].
root = [1,null,2,3][1,3,2]Example 1, root = [1,null,2,3]. The columns show the state after each row:
| Step | What runs | stack (bottom to top) | node | result | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [1] | None | [] | 1 is pushed, not visited: its left subtree comes first |
| 2 | node = stack.pop(), result.append(node.val), node = node.right | [] | 2 | [1] | 1 has no left subtree, so it is visited now; the walk goes right |
| 3 | Dive: push 2, then push 3 | [2, 3] | None | [1] | 3 is the left child of 2, so 2 must wait |
| 4 | Pop 3, append, node = node.right | [2] | None | [1, 3] | 3 is visited before 2 |
| 5 | Pop 2, append, node = node.right | [] | None | [1, 3, 2] | node is None and stack is empty, so the loop ends |
Appending when a node is pushed would add 1, then 2, then 3, and return the preorder [1, 2, 3].
| 1 | A depth-first walk reaches each node three times: on the way down, after its left subtree, and after its right subtree. The order name says which time lists the node. |
| 2 | Keep `stack` and `node = root`, and loop `while node or stack`: an inner `while node` pushes and moves to `node.left`, then pop, append `node.val` and move to `node.right`. |
| 3 | Preorder appends at the push, inorder at the pop, and postorder only when `top.right` is empty or `top.right is last`. |
| 4 | The trap: append after the pop in inorder. Appending at the push returns the preorder, `[1, 2, 3]` instead of `[1, 3, 2]` on `[1,null,2,3]`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A tree has no first, second and third element, so a list of its nodes needs a rule for the order. A depth-first walk reaches every node three times: on the way down, when it comes back from the left subtree, and when it comes back from the right subtree. The three visit orders differ only in which of those times adds the node to the list. Preorder lists the node on the way down, inorder after its left subtree, and postorder after its right subtree.
📚 The Analogy: A Folder Tree
A folder holds files and other folders. To copy the tree you create each folder before the things inside it: that is preorder. To delete the tree you remove the things inside a folder before the folder itself, because a folder with contents cannot be removed: that is postorder. Inorder needs two children, so it fits a binary tree: the node comes between its left and right subtrees. In a binary search tree that is exactly sorted order.
🔑 Why It Works
Recursion keeps the nodes that are waiting for the walk to come back in the call stack. An explicit stack keeps the same nodes in a list that you control. The inner loop pushes every node on the way down the left edge, so the node that stack.pop() returns has a finished left subtree. Appending its value right after the pop lists it between its two subtrees, and node = node.right starts the right subtree. Each node is pushed once and popped once.
Appending
node.valwhennodeis pushedLooping
while stackinstead ofwhile node or stackPopping a node in postorder without checking
top.right is not lastComparing
top.right.valwithlast.valinstead of the nodesWalking a deep tree with recursion
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Return the inorder traversal of its nodes' values" names an order, and the follow-up asks for the walk without recursion. A list of the nodes in a named visit order is Tree Traversals: one walk, with the visit placed at the moment the order name says.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before each stack.pop(), every value in result comes before every node still on stack, in inorder. The popped node has a finished left subtree, so result.append(node.val) adds the next value, and node = node.right starts the right subtree.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
result.append(node.val)goes afterstack.pop(), never next tostack.append(node). At the push, the list is the preorder,[1, 2, 3]instead of[1, 3, 2]on[1,null,2,3].while node or stack, neverwhile stack:stackis empty at the start, sowhile stackreturns[].root = []givesnode = Noneand an emptystack, so the loop never runs andresultis[]. Code that readsroot.valfirst fails on this input.The recursion is safe here, because the tree has at most 100 nodes. A chain of 3000 nodes raises RecursionError, which is why the explicit
stackis the form to know.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Tree Traversals on an explicit stack. Inorder means left subtree, then the node, then the right subtree. I keep a stack of the nodes whose left subtree is still being walked. From a node, I push it and move to its left child, again and again, until there is no left child. Then I pop one node. Its left subtree is finished, so I append its value to the result. Then I move to its right child, and the same dive starts again. The loop runs while there is a current node or the stack is not empty, because the stack can be empty while a right subtree is still waiting. The trap is where I append: after the pop, never at the push, or I would return the preorder. Each node is pushed once and popped once, so the time is order N, and the stack holds at most the height of the tree, so the space is order H.
Complexity & Mathematical Proof
O(N)
Look at the code: the inner while node: loop pushes one node per pass, and the outer loop pops one node per pass. A node is pushed when the walk first reaches it, and it is popped once, after its left subtree. Nothing pushes a node a second time, because node = node.right moves to a node that has never been pushed. So the walk makes N pushes and N pops, and each push, pop and append is O(1). Total: O(N).
O(H) stack
Every node on stack is an ancestor of node whose left subtree is still being walked, so stack holds at most one root-to-leaf path: O(H) nodes, where H is the height of the tree. The returned list holds N values; it is the output and is not counted.
Derivation Progression
N pushes
stack.append(node) runs once for each node, when the dive reaches it.
N pops and N appends
Each pass of while node or stack: pops one node and appends its value; the loop ends when every node has been popped.
N assignments
node = node.right runs once per pop and moves to a subtree that has not been pushed yet.
O(N)
Each push, pop, append and assignment is O(1).
Variable Definitions
Number of nodes in the tree (0 to 100 here)
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(1): iterative, no recursion
O(H): stack holds one root-to-leaf path at most
O(N): the returned list (not counted)
Boundary Best / Worst Cases
: every node is visited, whatever the shape
time and stack on a balanced tree
time; the stack grows to on a chain that leans left
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "inorder traversal", "could you do it iteratively?". A named visit order plus a request to avoid recursion: Tree Traversals with an explicit stack.
nodes and values in . One walk is time, and stack holds one root-to-node path, , which is at most 100 here, so recursion would also work. Binary Search Tree Iterator (LC 173) allows nodes in one chain, which passes Python's default recursion limit of 1000.
Appending node.val at the push returns the preorder, and while stack never starts. A walk that is paused between calls, such as an iterator, must keep stack and node as fields of an object, because local variables are lost when the function returns.