Iterative Traversal of Binary Trees
Master iterative binary tree traversal in Python! Learn how to implement pre-order, in-order, and post-order traversals using explicit stacks. Understand the key differences between recursive and iterative approaches, with clear examples and step-by-step visualizations.
Introduction
Previously I wrote a post about the recusive traversal of binary tree:
Fanyang Meng
Why should we consider using iterative methods (non-recursive approaches) for traversing binary trees? The answer lies in understanding how recursion works behind the scenes.
When we use recursion, each recursive call pushes local variables, parameter values, and return addresses onto the call stack. As the recursion unwinds, these values are popped from the stack top, allowing the program to return to previous positions in the execution flow. Understanding this mechanism reveals why we can use an explicit stack to implement binary tree traversals iteratively.
Pre-order Traversal (Iterative Approach)
Let's start with pre-order traversal.
Pre-order traversal follows the pattern: root-left-right. Since we process the root node first, we can start by pushing it onto our stack. Then, we'll push the right child followed by the left child.
Why push the right child before the left? Because when we pop from the stack, we want to process nodes in root-left-right order, and stacks follow Last-In-First-Out (LIFO) behavior.
flowchart TD
subgraph Tree
A1((1)) --> B1((2))
A1 --> C1((3))
B1 --> D1((4))
B1 --> E1((5))
end
subgraph Step1["Step 1: Push root"]
S1["Stack: [1]"]
R1["Result: []"]
end
subgraph Step2["Step 2: Pop 1, push right then left"]
S2["Stack: [3,2]"]
R2["Result: [1]"]
note2["1 popped and processed
right child (3) pushed first
left child (2) pushed last"]
end
subgraph Step3["Step 3: Pop 2, push its right then left"]
S3["Stack: [3,5,4]"]
R3["Result: [1,2]"]
note3["2 popped and processed
right child (5) pushed first
left child (4) pushed last"]
end
subgraph Step4["Step 4: Pop 4, process it"]
S4["Stack: [3,5]"]
R4["Result: [1,2,4]"]
note4["4 popped and processed
no children to push"]
end
subgraph Step5["Step 5: Continue until stack empty"]
S5["Stack: []"]
R5["Result: [1,2,4,5,3]"]
end
Step1 --> Step2
Step2 --> Step3
Step3 --> Step4
Step4 --> Step5
Here's the Python implementation (note that we don't push None nodes onto the stack):
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
# Process root node first
result.append(node.val)
# Push right child first (will be processed later)
if node.right:
stack.append(node.right)
# Push left child last (will be processed sooner)
if node.left:
stack.append(node.left)
return resultWhile this implementation might seem straightforward, you might wonder: "Can we modify this code slightly to implement in-order traversal?"
Actually, we can't! The reason becomes clear when we look at in-order traversal.
In-order Traversal (Iterative Approach)
To understand why the pre-order approach doesn't work for in-order traversal, we need to distinguish between two operations:
- Processing: Adding elements to our result list
- Visiting: Traversing through nodes
In pre-order traversal, we visit and process nodes in the same order (root-left-right), which allows for a simpler implementation. However, in-order traversal (left-root-right) requires us to visit nodes in one order but process them in another.
flowchart TD
subgraph Tree
A1((1)) --> B1((2))
A1 --> C1((3))
B1 --> D1((4))
B1 --> E1((5))
end
subgraph Step1["Step 1: Push left path from root"]
S1["Stack: [1,2,4]"]
curr1["Current: null"]
R1["Result: []"]
note1["Pushed 1,2,4 while following left path"]
end
subgraph Step2["Step 2: Process leftmost"]
S2["Stack: [1,2]"]
curr2["Current: right of 4 (null)"]
R2["Result: [4]"]
note2["Pop 4, add to result,
move to its right"]
end
subgraph Step3["Step 3: Process parent"]
S3["Stack: [1]"]
curr3["Current: right of 2 (5)"]
R3["Result: [4,2]"]
note3["Pop 2, add to result,
move to its right"]
end
subgraph Step4["Step 4: Handle right child"]
S4["Stack: [1]"]
curr4["Current: null"]
R4["Result: [4,2,5]"]
note4["Process 5,
no right child"]
end
subgraph Step5["Step 5: Process root"]
S5["Stack: []"]
curr5["Current: right of 1 (3)"]
R5["Result: [4,2,5,1]"]
note5["Pop 1, add to result,
move to its right"]
end
subgraph Step6["Final Step"]
S6["Stack: []"]
curr6["Current: null"]
R6["Result: [4,2,5,1,3]"]
note6["Process 3,
traversal complete"]
end
Step1 --> Step2
Step2 --> Step3
Step3 --> Step4
Step4 --> Step5
Step5 --> Step6
For in-order traversal, we need to visit nodes from top to bottom until we reach the leftmost leaf, but we can't process them until we've finished exploring the left subtree. This mismatch between visiting and processing order requires a different approach using a pointer to track our current position:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = []
result = []
current = root
while current or stack:
# Traverse to leftmost node
while current:
stack.append(current)
current = current.left
# Process current node and move to right subtree
current = stack.pop()
result.append(current.val)
current = current.right
return resultPost-order Traversal (Iterative Approach)
Post-order traversal follows the left-right-root pattern. Here's a clever approach: if we modify our pre-order traversal to follow a root-right-left pattern and then reverse the result, we'll get the left-right-root order we want!
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
# Push left child first (will be processed later)
if node.left:
stack.append(node.left)
# Push right child last (will be processed sooner)
if node.right:
stack.append(node.right)
# Reverse to get left-right-root order
return result[::-1]Workflow:
flowchart TD
subgraph Tree
A1((1)) --> B1((2))
A1 --> C1((3))
B1 --> D1((4))
B1 --> E1((5))
end
subgraph Step1["Step 1: Push root"]
S1["Stack: [1]"]
R1["Result: []"]
note1["Initial state"]
end
subgraph Step2["Step 2: Pop 1, add to result, push left & right"]
S2["Stack: [2,3]"]
R2["Result: [1]"]
note2["Pop 1, add to result
Push left(2) first
Push right(3) last"]
end
subgraph Step3["Step 3: Pop 3, add to result"]
S3["Stack: [2]"]
R3["Result: [1,3]"]
note3["Pop 3, add to result
No children to push"]
end
subgraph Step4["Step 4: Pop 2, add to result, push children"]
S4["Stack: [4,5]"]
R4["Result: [1,3,2]"]
note4["Pop 2, add to result
Push left(4) first
Push right(5) last"]
end
subgraph Step5["Step 5: Process remaining nodes"]
S5["Stack: [4]"]
R5["Result: [1,3,2,5]"]
note5["Pop 5, add to result
No children to push"]
end
subgraph Step6["Step 6: Final node and reverse"]
S6["Stack: []"]
R6["Initial: [1,3,2,5,4]
Final: [4,5,2,3,1]"]
note6["Pop 4, add to result
Reverse array to get
post-order traversal"]
end
Step1 --> Step2
Step2 --> Step3
Step3 --> Step4
Step4 --> Step5
Step5 --> Step6
Conclusion
We've now implemented all three traversal methods iteratively, and you might notice that pre-order and in-order implementations look quite different. This contrasts with recursive implementations, where the code structures are very similar.
The key insight is that pre-order traversal allows simultaneous visiting and processing of nodes, while in-order traversal requires us to handle these operations separately. This fundamental difference leads to distinct implementation approaches.
In practice, while recursive implementations are often more intuitive, understanding these iterative approaches provides valuable insights into tree traversal algorithms and can be useful in scenarios where stack space is a concern or when explicit stack control is needed.
A natural follow-up question might be: "Is it possible to implement all three traversal methods using a unified iterative approach?" Indeed it is, but that's a topic for another discussion, as it involves a more complex but more general algorithm that works for all three traversal orders.
Discussion