Binary Tree Inorder Traversal
Problem statement
You are given the root of a binary tree. Return the values of its nodes in inorder: visit the whole left subtree first, then the node itself, then the whole right subtree.
This order matters beyond being "just recursion" — for a binary search tree, an inorder walk visits the values from smallest to largest, so it is how you read a BST back out in sorted order.
Examples
Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation: Node 1 has no left child, so it is visited first. Its right subtree is node 2, which has a left child 3 and no right child, so inside that subtree 3 is visited before 2. That gives [1, 3, 2].

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: The left subtree of 1 (rooted at 2) is visited first and yields 4, 2, 6, 5, 7 in that order, then 1 itself, then the right subtree (rooted at 3) yields 3, 9, 8.

Hints
Approach
Optimal: Morris traversal
Intuition
The stack in the previous approach exists for one reason: to remember which node to return to after finishing a left subtree. Morris traversal stores that same information directly in the tree instead of in a separate structure. For a node with a left child, find the rightmost node in that left subtree (its inorder predecessor) — its right pointer is normally unused (it is the deepest-right node there), so temporarily point it back at the current node. Now walking left, then eventually right, naturally leads back to where you started, at which point you undo the link so the tree is left exactly as it was found. This removes the need for a stack entirely, at the cost of briefly mutating the tree.
Steps
- Start with
currat the root. - If
currhas no left child, record its value and move tocurr.right. - If
currhas a left child, find that subtree's rightmost node (pred), walking right fromcurr.leftuntil hitting a node whose right pointer is empty or already points back atcurr. - If
pred.rightis empty, setpred.right = curr(create the temporary link) and movecurrtocurr.left. - If
pred.rightalready points atcurr, the left subtree has been fully visited: remove the link (pred.right = None), recordcurr's value, and move tocurr.right. - Repeat until
currbecomes empty.
Dry run
root = [1, null, 2, 3]
| step | curr | left child? | predecessor's right | action |
|---|---|---|---|---|
| 1 | 1 | no (1 has no left child) | — | record 1, curr = 1.right = 2 |
| 2 | 2 | yes (3) | pred = 3; 3.right is empty | link 3.right → 2, curr = 2.left = 3 |
| 3 | 3 | no | — | record 3, curr = 3.right = 2 (the link just made) |
| 4 | 2 | yes (3) | pred = 3; 3.right already points at 2 | remove link, record 2, curr = 2.right = null |
Recorded in order: [1, 3, 2], and the tree's original shape (3 back to having no right child) is restored.
Edge cases: an empty tree returns [] immediately. A node with no left child anywhere along the path (a right-leaning chain) never creates a temporary link and behaves like a plain walk down the right pointers.
Complexity
Time O(n) - Even though nodes can be revisited while their left subtree's rightmost pointer is located, each edge in that search is walked at most twice across the whole run (once to create the temporary link, once to remove it), so the total work stays linear.
Space O(1) - No stack and no recursion. The only extra memory is a couple of pointers; the tree itself is used, temporarily, to store the "come back here" information that the stack held in the previous approach.
class Solution:
def inorderTraversal(self, root: "TreeNode | None") -> list[int]:
res: list[int] = []
curr = root
while curr is not None:
if curr.left is None:
res.append(curr.val)
curr = curr.right
else:
pred = curr.left
while pred.right is not None and pred.right is not curr:
pred = pred.right
if pred.right is None:
pred.right = curr
curr = curr.left
else:
pred.right = None
res.append(curr.val)
curr = curr.right
return res
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(values):
from collections import deque
if not values or values[0] is None:
return None
root = TreeNode(values[0])
queue = deque([root])
i = 1
n = len(values)
while queue and i < n:
node = queue.popleft()
if i < n:
v = values[i]
i += 1
if v is not None:
node.left = TreeNode(v)
queue.append(node.left)
if i < n:
v = values[i]
i += 1
if v is not None:
node.right = TreeNode(v)
queue.append(node.right)
return root
def fmt(values: list[int]) -> str:
return "[" + ",".join(str(x) for x in values) + "]"
if __name__ == "__main__":
root1 = build_tree([1, None, 2, 3])
root2 = build_tree([1, 2, 3, 4, 5, None, 8, None, None, 6, 7, 9])
sol = Solution()
print(fmt(sol.inorderTraversal(root1))) # [1,3,2]
print(fmt(sol.inorderTraversal(root2))) # [4,2,6,5,7,1,3,9,8]RecapThe whole problem in a few lines, for the night before
- Spot it: "return the values of a binary tree in left-root-right order" — this is inorder traversal, and it is how a BST yields sorted values
- Idea: go as far left as possible, visit, then step right one node — done with recursion, an explicit stack, or by briefly threading unused right pointers (Morris)
- Cost: O(n) time in every approach; O(h) space for recursion or an explicit stack (up to O(n) for a skewed tree), O(1) extra space for Morris traversal
- Trap: forgetting to remove the temporary link in Morris traversal leaves the tree mutated after the function returns
Interview follow-ups
The tree can have a million nodes and might be badly skewed. Recursion risks a stack overflow — what do you do?
Switch to the iterative version with an explicit stack, or go further and use Morris traversal. The explicit stack moves the same O(h) memory from the language's call stack (which has a fixed, often small limit) to your own heap-allocated structure, which can grow as large as available memory allows. Morris traversal removes that concern entirely by using O(1) extra space, at the cost of temporarily mutating the tree while it runs, which is only safe if no other thread reads the tree at the same time.
Instead of returning the whole list, process each value as soon as you visit it, without holding the full result in memory.
The iterative (stack) and Morris approaches already visit nodes one at a time in the correct order, so replace
res.append(curr.val)with a call to whatever consumer needs the value — a callback, a generatoryield, or writing it straight to output. This drops the O(n) memory used to hold the final list; the iterative version still needs O(h) for the stack, but Morris needs no extra memory at all, which matters when you are streaming values out of a tree too large to build a full result list for.
Frequently asked questions
Recursion relies on the language's call stack, which has a limited depth. A very deep or deliberately skewed tree (essentially a linked list of a few hundred thousand nodes) can blow that stack, and interviewers ask for the iterative version specifically to see whether you can replace implicit recursion with an explicit stack. The same substitution comes up in production when you parse deeply nested JSON or recurse over a directory tree that a user fully controls.
It temporarily turns the tree into a linked structure that remembers its own "return path." For a node with a left child, it threads that subtree's rightmost node's right pointer back to the current node, walks down, does the visit when it detects that thread, and then removes it. The net effect is inorder traversal with no stack and no recursion, at the cost of briefly mutating the tree while the algorithm runs.
Configuration and dependency structures are frequently trees: a directory tree, a Terraform module graph, a Kubernetes owner-reference chain. Inorder traversal specifically is the way a binary search tree yields values in sorted order, so understanding it is the base case for range queries and ordered iteration over that kind of structure.
All three visit the same three parts (node, left subtree, right subtree) in a different order: preorder is node-left-right, inorder is left-node-right, and postorder is left-right-node. Preorder is useful for copying or serializing a tree top-down; postorder is useful when you must finish with a node's children before doing anything with the node itself, such as deleting a tree or computing a size that depends on both subtrees.
No — it is defined for any binary tree and this problem does not promise the input is a BST. It only produces sorted output when the input happens to be a valid BST; on a general binary tree it is still a well-defined visiting order, just not a sorted one.