Tree Traversals (Recursive and Iterative)
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?
Tree Traversals
Tree ➔ Stack Walk (Pre, In or Post) ➔ Nodes In That Order| 1 | from typing import Callable, Literal, Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | |
| 10 | def traverse(root: Optional[TreeNode], order: Literal["pre", "in", "post"], visit: Callable[[TreeNode], None]) -> None: |
| 11 | """Depth-First Traversal with an explicit stack: visit(node) is called once for |
| 12 | every node, in the chosen order. |
| 13 | "pre" visits a node before its two subtrees, "in" between them, and "post" after |
| 14 | both. |
| 15 | Precondition: visit needs only the node itself, and it does not change the tree. |
| 16 | N = number of nodes. H = height. T = the cost of one visit call. |
| 17 | Time: O(N * T) | Space: O(H) stack |
| 18 | """ |
| 19 | # Nodes the walk has pushed and not popped yet; the deepest node is on top |
| 20 | stack: list[TreeNode] = [] |
| 21 | # The node popped most recently; "post" reads it to see that a right subtree is |
| 22 | # finished |
| 23 | last: Optional[TreeNode] = None |
| 24 | node = root |
| 25 | while node or stack: |
| 26 | # 1. Dive Left: |
| 27 | # Push every node on the way down the left edge. "pre" visits each node here, |
| 28 | # before both of its subtrees. |
| 29 | while node: |
| 30 | if order == "pre": |
| 31 | visit(node) |
| 32 | stack.append(node) |
| 33 | node = node.left |
| 34 | |
| 35 | # 2. Finish The Right Subtree First ("post" only): |
| 36 | # "post" visits a node after both subtrees. If the right subtree is not |
| 37 | # finished, walk it before popping. |
| 38 | top = stack[-1] |
| 39 | if order == "post" and top.right and top.right is not last: |
| 40 | node = top.right |
| 41 | continue |
| 42 | |
| 43 | # 3. Pop The Node: |
| 44 | # The walk is done with the left subtree, and for "post" with the right subtree |
| 45 | # too. "in" and "post" visit the node now. "pre" and "in" then move to the right |
| 46 | # subtree. |
| 47 | stack.pop() |
| 48 | if order != "pre": |
| 49 | visit(top) |
| 50 | last = top |
| 51 | if order != "post": |
| 52 | node = top.right |
stack holds the nodes the walk has pushed and not popped yet, deepest on top. visit is called once for every node, at the point order names: before its two subtrees, between them, or after both.The walk reaches every node three times: on the way down, after the left subtree is finished, and after the right subtree is finished. The order name says which of the three times calls visit. Preorder visits on the way down, inorder after the left subtree, and postorder after the right subtree. So one stack serves all three orders, and only the line that calls visit moves. 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, and node = node.right walks its right subtree next. Every node is pushed once and popped once, so it is visited once. Postorder is the one order that comes back to a node twice before it leaves, so the template pops a node only when top.right is empty or top.right is last. The trap is where the visit line sits. In inorder, result.append(node.val) goes right after stack.pop(). Next to stack.append(node), it runs on the way down and returns the preorder: [1, 2, 3] instead of [1, 3, 2] on [1,null,2,3].
See it run
Inorder walk on an explicit stack, step by step
node 1stack size 0inorder []preorder []
Each circle is a tree node. The stack row has its top on the right. The preorder list takes a node when it is pushed. The inorder list takes it when it is popped.
nodethe node the loop moves to nexton stackpushed, and waiting for its left subtree to finishvisitedpopped and added to the inorder list
Start at the root 1. Dive left and push every node on the way down.
Gotcha 1 of 5
- The trap
Gotcha 1: Appending
node.valwhennodeis pushedMistakewhile node: result.append(node.val) stack.append(node) node = node.left node = stack.pop()Fixwhile node: stack.append(node) node = node.left node = stack.pop() result.append(node.val)What happens: A pushed node has not yet had its left subtree visited. The pushes go from the root down the left edge, so every value is appended before the smaller values that belong in front of it. The list that results is the preorder. On
[1,null,2,3], the walk appends 1, then pushes and appends 2, then pushes and appends 3. The result is[1, 2, 3]. The inorder is[1, 3, 2], because 3 is the left child of 2.Example: Binary Tree Inorder Traversal (LC 94): root = [1,null,2,3]Mistake: returns [1, 2, 3]Fix: returns [1, 3, 2]
- The tree is a BST and the answer is one value at a given rank, as in Kth Smallest Element in a BST (LC 230): the inorder walk stops at the k-th visit instead of listing every node. See BST Inorder
- You need one number for the whole tree, as in Maximum Depth of Binary Tree (LC 104), not a list of nodes: each call returns an answer built from the answers of its two subtrees. See Bottom-Up DFS
- Each node needs a value from the path above it, as in Path Sum (LC 112): the running sum travels down in an argument, and the order of the visits does not matter. See Top-Down DFS
- The nodes must come out one level at a time, as in Binary Tree Level Order Traversal (LC 102), not one branch at a time: a queue replaces the stack. See Level-Order BFS
Deep Dive
The three times the walk reaches a node, and which time lists it
A depth-first walk reaches every node three times. The first time is when the walk arrives from the parent. The second time is when the walk comes back from the left subtree. The third time is when the walk comes back from the right subtree. A node with no left child still has a second time, right after the first.
The three orders differ in one thing: which time adds the node to the list. Preorder lists the node the first time. Inorder lists it the second time. Postorder lists it the third time. The walk itself is the same in all three.
Example: in Binary Tree Inorder Traversal (LC 94), take root = [1,2,3,4,5,null,8,null,null,6,7,9]. The preorder is [1, 2, 4, 5, 6, 7, 3, 8, 9]. The inorder is [4, 2, 6, 5, 7, 1, 3, 9, 8]. The postorder is [4, 6, 7, 5, 2, 9, 8, 3, 1]. Node 1 is first in the preorder. It is sixth in the inorder, after the five nodes of its left subtree. It is last in the postorder.
How the explicit stack replaces the call stack
A recursive walk keeps the nodes that wait for the walk to come back in the call stack. Each call is one waiting node. Python allows about 1000 nested calls by default, so a deep tree raises RecursionError. The blueprint keeps the same waiting nodes in a list named stack. The list lives on the heap, so the limit is the memory of the program.
The inner loop pushes every node on the way down the left edge. Each pushed node waits for its left subtree. stack.pop() returns the deepest waiting node, so its left subtree is finished. That is the second time the walk reaches the node, and result.append(node.val) runs right after it. Then node = node.right starts the right subtree, and the next pass dives left inside it.
Example: take root = [1,null,2,3]. The walk pushes 1. It pops 1 and appends it, and then moves to the right child 2. It pushes 2 and 3. It pops 3 and appends it. It pops 2 and appends it. The result is [1, 3, 2].
The outer condition is while node or stack. The stack is empty at the start, and it is empty again after 1 is popped in this example, while node points at the right child 2. A test on stack alone stops too early.
Moving the visit: preorder, inorder and postorder
The template shares the dive-left loop in all three orders. For preorder, call visit(node) inside the dive loop, at the push. For inorder, call visit(top) right after stack.pop(). In both orders the walk then moves to top.right.
Postorder is different, because a node comes to the top of the stack twice before it may leave. The first time is after its left subtree. The second time is after its right subtree. The template reads top = stack[-1] first. It pops top only when top.right is empty or top.right is last. last is the node popped most recently. The last node popped from any subtree is the root of that subtree, so top.right is last means that the right subtree is finished.
Example: postorder of [1,null,2,3]. The walk dives to 1. Node 1 has a right child 2 that is not last, so the walk goes into 2 and dives to 3. Node 3 has no right child, so it is popped and visited. Then 2 has no right child, so it is popped and visited. Then top is 1, and 1.right is 2, which is last. So 1 is popped and visited. The result is [3, 2, 1].
The test compares nodes with is not. A test on values fails when values repeat. On [1,1,1], a value test decides that the right child is already finished, and the result is [1, 1] instead of [1, 1, 1].
What each order is for, and what the walk costs
Preorder lists a parent before its children. It fits copying a tree and writing it down so that it can be rebuilt, because the first value is the root. Construct Binary Tree from Preorder and Inorder Traversal (LC 105) uses the preorder to name each root.
Inorder lists the left subtree, the node, then the right subtree. In a binary search tree this is sorted order. Kth Smallest Element in a BST (LC 230) stops at the k-th value. Binary Search Tree Iterator (LC 173) keeps stack and node between calls. next() pops the top, dives left from its right child, and returns the popped value. hasNext() tests that stack is not empty.
Postorder lists the children before the parent. It fits deleting a tree, because a node can be removed only after everything below it is removed. It also fits any answer that is built from the answers of the subtrees, such as the depth in Maximum Depth of Binary Tree (LC 104).
All three orders push each node once and pop it once, so the time is O(N). The stack holds one root-to-node path, so the space is O(H), where H is the height. For a chain, H is N. The list of results is the output and is not counted.
60-Second Pitch
"A depth-first walk reaches every node three times: on the way down, after the left subtree, and after the right subtree. The order name only says which of the three times lists the node. I walk with an explicit stack. The inner loop pushes every node on the way down the left edge. Then I pop. The popped node has a finished left subtree, so for inorder I list it now, and I move to its right child. For preorder, I list the node at the push. For postorder, I pop a node only when its right subtree is finished, and I use a last node to know that. The time is O(N), because each node is pushed and popped once. The space is O(H) for the stack."
Common Questions
- Which traversal order should I use for which job?
Use preorder when a parent must come before its children, for example to copy a tree or to write it down so it can be rebuilt. Use inorder on a binary search tree to read the values in sorted order. Use postorder when the children must be finished before the parent, for example to delete a tree or to build an answer from the answers of the subtrees.
- How do you write inorder without recursion?
Keep a
stackand a currentnode. Whilenodeorstackhas something left, pushnodeand move tonode.leftuntil there is no node. Then pop, append the popped value, and setnode = node.right. Each node is pushed once and popped once, so the time isO(N).- How do you write postorder with a stack? Is there a shorter way?
The template keeps a
lastnode and pops a node only when its right child is empty or islast. A shorter way works when you only need the list of values. Run a preorder that visits the node, then pushes the left child, then the right child, so the right child is popped first. That gives node, right, left. Reverse the list to get left, right, node, which is the postorder. The visits do not happen in postorder in time, so use it only when the values can be collected first.- How do you adapt this to a tree where a node has many children?
In N-ary Tree Preorder Traversal (LC 589), pop a node, list it, and push its children in reverse order, so the first child is popped first. In N-ary Tree Postorder Traversal (LC 590), run the same loop with the children pushed in their normal order. That lists node, last child, ..., first child. Reverse the list to get the postorder. Both give the LeetCode example answers,
[1, 3, 5, 6, 2, 4]and[5, 6, 3, 2, 4, 1].- Can a traversal use
O(1)extra space instead of O(H)? Yes. Morris traversal links the last node of a node's left subtree back to the node with a temporary right pointer, so the walk can climb back up without a stack. It removes each link when it uses it. The time is still
O(N). The cost is that the tree is changed while the walk runs, so it is not safe when another reader uses the same tree.
SWE Reasoning
Spot it
- The statement names an order for the nodes: preorder, inorder or postorder.
- The statement asks for the walk without recursion, or the tree can be too deep for recursion.
- The nodes must come out one at a time, as in an iterator that is paused between calls.
- The answer is a list of nodes, not one number for the whole tree.
- The tree is a BST and the values must come out in sorted order.
The invariant, step by step
stackholds the nodes the walk has pushed and not popped yet. The deepest node is on top.- The inner loop pushes every node on the way down the left edge, so each pushed node waits for its left subtree.
stack.pop()returns the top. Its left subtree is finished, so the top is the next node in inorder.result.append(node.val)lists it. Thennode = node.rightstarts the right subtree.- The loop runs while
nodeorstackhas something left, so no node is skipped. - Each node is pushed once and popped once, so each node is listed once.
Traps
- Listing at the push. In inorder, the value goes right after the pop. At the push, the list is the preorder.
while stackas the outer loop. The stack is empty at the start, so the loop never runs. Usewhile node or stack.- Popping in postorder too early. A node must wait until
top.rightis empty ortop.right is last. - Comparing values instead of nodes. Values repeat, so use
is not. - Recursion on a deep tree. A chain of 3000 nodes raises
RecursionErrorin Python.
Practice
Tree Traversals (Recursive and Iterative)
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?
Tree Traversals
Tree ➔ Stack Walk (Pre, In or Post) ➔ Nodes In That Order| 1 | from typing import Callable, Literal, Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | |
| 10 | def traverse(root: Optional[TreeNode], order: Literal["pre", "in", "post"], visit: Callable[[TreeNode], None]) -> None: |
| 11 | """Depth-First Traversal with an explicit stack: visit(node) is called once for |
| 12 | every node, in the chosen order. |
| 13 | "pre" visits a node before its two subtrees, "in" between them, and "post" after |
| 14 | both. |
| 15 | Precondition: visit needs only the node itself, and it does not change the tree. |
| 16 | N = number of nodes. H = height. T = the cost of one visit call. |
| 17 | Time: O(N * T) | Space: O(H) stack |
| 18 | """ |
| 19 | # Nodes the walk has pushed and not popped yet; the deepest node is on top |
| 20 | stack: list[TreeNode] = [] |
| 21 | # The node popped most recently; "post" reads it to see that a right subtree is |
| 22 | # finished |
| 23 | last: Optional[TreeNode] = None |
| 24 | node = root |
| 25 | while node or stack: |
| 26 | # 1. Dive Left: |
| 27 | # Push every node on the way down the left edge. "pre" visits each node here, |
| 28 | # before both of its subtrees. |
| 29 | while node: |
| 30 | if order == "pre": |
| 31 | visit(node) |
| 32 | stack.append(node) |
| 33 | node = node.left |
| 34 | |
| 35 | # 2. Finish The Right Subtree First ("post" only): |
| 36 | # "post" visits a node after both subtrees. If the right subtree is not |
| 37 | # finished, walk it before popping. |
| 38 | top = stack[-1] |
| 39 | if order == "post" and top.right and top.right is not last: |
| 40 | node = top.right |
| 41 | continue |
| 42 | |
| 43 | # 3. Pop The Node: |
| 44 | # The walk is done with the left subtree, and for "post" with the right subtree |
| 45 | # too. "in" and "post" visit the node now. "pre" and "in" then move to the right |
| 46 | # subtree. |
| 47 | stack.pop() |
| 48 | if order != "pre": |
| 49 | visit(top) |
| 50 | last = top |
| 51 | if order != "post": |
| 52 | node = top.right |
stack holds the nodes the walk has pushed and not popped yet, deepest on top. visit is called once for every node, at the point order names: before its two subtrees, between them, or after both.The walk reaches every node three times: on the way down, after the left subtree is finished, and after the right subtree is finished. The order name says which of the three times calls visit. Preorder visits on the way down, inorder after the left subtree, and postorder after the right subtree. So one stack serves all three orders, and only the line that calls visit moves. 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, and node = node.right walks its right subtree next. Every node is pushed once and popped once, so it is visited once. Postorder is the one order that comes back to a node twice before it leaves, so the template pops a node only when top.right is empty or top.right is last. The trap is where the visit line sits. In inorder, result.append(node.val) goes right after stack.pop(). Next to stack.append(node), it runs on the way down and returns the preorder: [1, 2, 3] instead of [1, 3, 2] on [1,null,2,3].
See it run
Inorder walk on an explicit stack, step by step
node 1stack size 0inorder []preorder []
Each circle is a tree node. The stack row has its top on the right. The preorder list takes a node when it is pushed. The inorder list takes it when it is popped.
nodethe node the loop moves to nexton stackpushed, and waiting for its left subtree to finishvisitedpopped and added to the inorder list
Start at the root 1. Dive left and push every node on the way down.
Gotcha 1 of 5
- The trap
Gotcha 1: Appending
node.valwhennodeis pushedMistakewhile node: result.append(node.val) stack.append(node) node = node.left node = stack.pop()Fixwhile node: stack.append(node) node = node.left node = stack.pop() result.append(node.val)What happens: A pushed node has not yet had its left subtree visited. The pushes go from the root down the left edge, so every value is appended before the smaller values that belong in front of it. The list that results is the preorder. On
[1,null,2,3], the walk appends 1, then pushes and appends 2, then pushes and appends 3. The result is[1, 2, 3]. The inorder is[1, 3, 2], because 3 is the left child of 2.Example: Binary Tree Inorder Traversal (LC 94): root = [1,null,2,3]Mistake: returns [1, 2, 3]Fix: returns [1, 3, 2]
- The tree is a BST and the answer is one value at a given rank, as in Kth Smallest Element in a BST (LC 230): the inorder walk stops at the k-th visit instead of listing every node. See BST Inorder
- You need one number for the whole tree, as in Maximum Depth of Binary Tree (LC 104), not a list of nodes: each call returns an answer built from the answers of its two subtrees. See Bottom-Up DFS
- Each node needs a value from the path above it, as in Path Sum (LC 112): the running sum travels down in an argument, and the order of the visits does not matter. See Top-Down DFS
- The nodes must come out one level at a time, as in Binary Tree Level Order Traversal (LC 102), not one branch at a time: a queue replaces the stack. See Level-Order BFS
Deep Dive
The three times the walk reaches a node, and which time lists it
A depth-first walk reaches every node three times. The first time is when the walk arrives from the parent. The second time is when the walk comes back from the left subtree. The third time is when the walk comes back from the right subtree. A node with no left child still has a second time, right after the first.
The three orders differ in one thing: which time adds the node to the list. Preorder lists the node the first time. Inorder lists it the second time. Postorder lists it the third time. The walk itself is the same in all three.
Example: in Binary Tree Inorder Traversal (LC 94), take root = [1,2,3,4,5,null,8,null,null,6,7,9]. The preorder is [1, 2, 4, 5, 6, 7, 3, 8, 9]. The inorder is [4, 2, 6, 5, 7, 1, 3, 9, 8]. The postorder is [4, 6, 7, 5, 2, 9, 8, 3, 1]. Node 1 is first in the preorder. It is sixth in the inorder, after the five nodes of its left subtree. It is last in the postorder.
How the explicit stack replaces the call stack
A recursive walk keeps the nodes that wait for the walk to come back in the call stack. Each call is one waiting node. Python allows about 1000 nested calls by default, so a deep tree raises RecursionError. The blueprint keeps the same waiting nodes in a list named stack. The list lives on the heap, so the limit is the memory of the program.
The inner loop pushes every node on the way down the left edge. Each pushed node waits for its left subtree. stack.pop() returns the deepest waiting node, so its left subtree is finished. That is the second time the walk reaches the node, and result.append(node.val) runs right after it. Then node = node.right starts the right subtree, and the next pass dives left inside it.
Example: take root = [1,null,2,3]. The walk pushes 1. It pops 1 and appends it, and then moves to the right child 2. It pushes 2 and 3. It pops 3 and appends it. It pops 2 and appends it. The result is [1, 3, 2].
The outer condition is while node or stack. The stack is empty at the start, and it is empty again after 1 is popped in this example, while node points at the right child 2. A test on stack alone stops too early.
Moving the visit: preorder, inorder and postorder
The template shares the dive-left loop in all three orders. For preorder, call visit(node) inside the dive loop, at the push. For inorder, call visit(top) right after stack.pop(). In both orders the walk then moves to top.right.
Postorder is different, because a node comes to the top of the stack twice before it may leave. The first time is after its left subtree. The second time is after its right subtree. The template reads top = stack[-1] first. It pops top only when top.right is empty or top.right is last. last is the node popped most recently. The last node popped from any subtree is the root of that subtree, so top.right is last means that the right subtree is finished.
Example: postorder of [1,null,2,3]. The walk dives to 1. Node 1 has a right child 2 that is not last, so the walk goes into 2 and dives to 3. Node 3 has no right child, so it is popped and visited. Then 2 has no right child, so it is popped and visited. Then top is 1, and 1.right is 2, which is last. So 1 is popped and visited. The result is [3, 2, 1].
The test compares nodes with is not. A test on values fails when values repeat. On [1,1,1], a value test decides that the right child is already finished, and the result is [1, 1] instead of [1, 1, 1].
What each order is for, and what the walk costs
Preorder lists a parent before its children. It fits copying a tree and writing it down so that it can be rebuilt, because the first value is the root. Construct Binary Tree from Preorder and Inorder Traversal (LC 105) uses the preorder to name each root.
Inorder lists the left subtree, the node, then the right subtree. In a binary search tree this is sorted order. Kth Smallest Element in a BST (LC 230) stops at the k-th value. Binary Search Tree Iterator (LC 173) keeps stack and node between calls. next() pops the top, dives left from its right child, and returns the popped value. hasNext() tests that stack is not empty.
Postorder lists the children before the parent. It fits deleting a tree, because a node can be removed only after everything below it is removed. It also fits any answer that is built from the answers of the subtrees, such as the depth in Maximum Depth of Binary Tree (LC 104).
All three orders push each node once and pop it once, so the time is O(N). The stack holds one root-to-node path, so the space is O(H), where H is the height. For a chain, H is N. The list of results is the output and is not counted.
60-Second Pitch
"A depth-first walk reaches every node three times: on the way down, after the left subtree, and after the right subtree. The order name only says which of the three times lists the node. I walk with an explicit stack. The inner loop pushes every node on the way down the left edge. Then I pop. The popped node has a finished left subtree, so for inorder I list it now, and I move to its right child. For preorder, I list the node at the push. For postorder, I pop a node only when its right subtree is finished, and I use a last node to know that. The time is O(N), because each node is pushed and popped once. The space is O(H) for the stack."
Common Questions
- Which traversal order should I use for which job?
Use preorder when a parent must come before its children, for example to copy a tree or to write it down so it can be rebuilt. Use inorder on a binary search tree to read the values in sorted order. Use postorder when the children must be finished before the parent, for example to delete a tree or to build an answer from the answers of the subtrees.
- How do you write inorder without recursion?
Keep a
stackand a currentnode. Whilenodeorstackhas something left, pushnodeand move tonode.leftuntil there is no node. Then pop, append the popped value, and setnode = node.right. Each node is pushed once and popped once, so the time isO(N).- How do you write postorder with a stack? Is there a shorter way?
The template keeps a
lastnode and pops a node only when its right child is empty or islast. A shorter way works when you only need the list of values. Run a preorder that visits the node, then pushes the left child, then the right child, so the right child is popped first. That gives node, right, left. Reverse the list to get left, right, node, which is the postorder. The visits do not happen in postorder in time, so use it only when the values can be collected first.- How do you adapt this to a tree where a node has many children?
In N-ary Tree Preorder Traversal (LC 589), pop a node, list it, and push its children in reverse order, so the first child is popped first. In N-ary Tree Postorder Traversal (LC 590), run the same loop with the children pushed in their normal order. That lists node, last child, ..., first child. Reverse the list to get the postorder. Both give the LeetCode example answers,
[1, 3, 5, 6, 2, 4]and[5, 6, 3, 2, 4, 1].- Can a traversal use
O(1)extra space instead of O(H)? Yes. Morris traversal links the last node of a node's left subtree back to the node with a temporary right pointer, so the walk can climb back up without a stack. It removes each link when it uses it. The time is still
O(N). The cost is that the tree is changed while the walk runs, so it is not safe when another reader uses the same tree.
SWE Reasoning
Spot it
- The statement names an order for the nodes: preorder, inorder or postorder.
- The statement asks for the walk without recursion, or the tree can be too deep for recursion.
- The nodes must come out one at a time, as in an iterator that is paused between calls.
- The answer is a list of nodes, not one number for the whole tree.
- The tree is a BST and the values must come out in sorted order.
The invariant, step by step
stackholds the nodes the walk has pushed and not popped yet. The deepest node is on top.- The inner loop pushes every node on the way down the left edge, so each pushed node waits for its left subtree.
stack.pop()returns the top. Its left subtree is finished, so the top is the next node in inorder.result.append(node.val)lists it. Thennode = node.rightstarts the right subtree.- The loop runs while
nodeorstackhas something left, so no node is skipped. - Each node is pushed once and popped once, so each node is listed once.
Traps
- Listing at the push. In inorder, the value goes right after the pop. At the push, the list is the preorder.
while stackas the outer loop. The stack is empty at the start, so the loop never runs. Usewhile node or stack.- Popping in postorder too early. A node must wait until
top.rightis empty ortop.right is last. - Comparing values instead of nodes. Values repeat, so use
is not. - Recursion on a deep tree. A chain of 3000 nodes raises
RecursionErrorin Python.