A
AiTechWorlds
AiTechWorlds
You are dropped into a maze. Your goal: visit every room. You have three strategies.
Strategy 1: Start at the entrance. Always take the leftmost unexplored path first. Go as deep as you can. When you hit a dead end, backtrack and try the next path. You are exploring depth-first, left-biased. This is in-order traversal.
Strategy 2: Start at the entrance. Note where you are first, then explore everything to the left, then everything to the right. You always process yourself before your branches. This is pre-order traversal.
Strategy 3: Explore the maze level by level. Visit every room on floor 1, then every room on floor 2, then floor 3. Always finish one level before going deeper. This is level-order (BFS) traversal.
Each strategy visits every room — but the order matters enormously. Different traversal orders reveal different properties of the tree and solve different problems.
All examples use this tree:
We expect these results:
from collections import deque
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Build: [4, 2, 6, 1, 3, 5, 7]
root = TreeNode(4)
root.left = TreeNode(2); root.right = TreeNode(6)
root.left.left = TreeNode(1); root.left.right = TreeNode(3)
root.right.left = TreeNode(5); root.right.right = TreeNode(7)
Rule: Recurse left, visit current, recurse right.
Key property: On a BST, in-order traversal always yields values in sorted ascending order.
# Recursive version
def inorder_recursive(node):
if node is None:
return
inorder_recursive(node.left) # Step 1: Go all the way left
print(node.val, end=" ") # Step 2: Visit current node
inorder_recursive(node.right) # Step 3: Then go right
# Iterative version (using an explicit stack)
def inorder_iterative(root):
stack = []
current = root
while current or stack:
while current: # Push all left nodes onto the stack
stack.append(current)
current = current.left
current = stack.pop() # Process the leftmost unvisited node
print(current.val, end=" ")
current = current.right # Then move to the right subtree
inorder_recursive(root)
print()
inorder_iterative(root)
Output:
1 2 3 4 5 6 7
1 2 3 4 5 6 7
Use cases: Sorting, getting values in ascending order from a BST, validating that a tree is a valid BST.
Rule: Visit current, recurse left, recurse right.
Key property: The root is always visited first. Sub-trees are fully described in top-down order.
# Recursive
def preorder_recursive(node):
if node is None:
return
print(node.val, end=" ") # Step 1: Visit current node FIRST
preorder_recursive(node.left) # Step 2: Then left subtree
preorder_recursive(node.right) # Step 3: Then right subtree
# Iterative (using a stack — push right first so left is processed first)
def preorder_iterative(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val, end=" ")
if node.right:
stack.append(node.right) # Push right first (processed second)
if node.left:
stack.append(node.left) # Push left second (processed first)
preorder_recursive(root)
print()
preorder_iterative(root)
Output:
4 2 1 3 6 5 7
4 2 1 3 6 5 7
Use cases: Copying a tree (create nodes in root-first order), serializing a tree structure to a file, prefix expression notation.
Rule: Recurse left, recurse right, visit current.
Key property: The root is always visited last. Children are fully processed before their parent.
# Recursive
def postorder_recursive(node):
if node is None:
return
postorder_recursive(node.left) # Step 1: Process entire left subtree
postorder_recursive(node.right) # Step 2: Process entire right subtree
print(node.val, end=" ") # Step 3: Visit current node LAST
# Iterative (two-stack method)
def postorder_iterative(root):
if not root:
return
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node) # Collect nodes in reverse post-order
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
print(stack2.pop().val, end=" ") # Pop gives correct post-order
postorder_recursive(root)
print()
postorder_iterative(root)
Output:
1 3 2 5 7 6 4
1 3 2 5 7 6 4
Use cases: Deleting a tree (delete children before the parent), calculating the size/height of a tree, evaluating expression trees (evaluate children before the operator).
Rule: Visit all nodes at depth 0, then depth 1, then depth 2, and so on.
Key property: Nodes are visited in order of their distance from the root.
def level_order(root):
if not root:
return
queue = deque([root]) # Start with the root in the queue
while queue:
node = queue.popleft() # Process the front of the queue
print(node.val, end=" ")
if node.left:
queue.append(node.left) # Add left child to back of queue
if node.right:
queue.append(node.right) # Add right child to back of queue
level_order(root)
Output:
4 2 6 1 3 5 7
Level by level with separation:
def level_order_by_level(root):
if not root:
return
queue = deque([root])
while queue:
level_size = len(queue) # Number of nodes at the current level
level_vals = []
for _ in range(level_size): # Process exactly this level's nodes
node = queue.popleft()
level_vals.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
print(level_vals)
level_order_by_level(root)
Output:
[4]
[2, 6]
[1, 3, 5, 7]
Use cases: Finding the shortest path, printing a tree level by level, checking if a tree is complete, connecting nodes at the same level.
| Traversal | Order | Tool | Output on [4,2,6,1,3,5,7] | Key Use Case |
|---|---|---|---|---|
| In-order | Left → Root → Right | Stack | 1 2 3 4 5 6 7 | Sorted output from BST |
| Pre-order | Root → Left → Right | Stack | 4 2 1 3 6 5 7 | Copy/serialize tree |
| Post-order | Left → Right → Root | 2 Stacks | 1 3 2 5 7 6 4 | Delete tree, expression eval |
| Level-order | Level by level | Queue | 4 2 6 1 3 5 7 | BFS, shortest path |
A tree is symmetric if the left subtree mirrors the right subtree. This requires comparing nodes on opposite sides simultaneously — a natural post-order-style recursive check.
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right: return True # Both empty — symmetric
if not left or not right: return False # One empty, one not — not symmetric
return (left.val == right.val and # Values must match
is_mirror(left.left, right.right) and # Outer pair
is_mirror(left.right, right.left)) # Inner pair
return is_mirror(root.left, root.right)
# Symmetric tree: Non-symmetric tree:
# 1 1
# / \ / \
# 2 2 2 2
# / \ / \ \ \
# 3 4 4 3 3 3
sym_root = TreeNode(1)
sym_root.left = TreeNode(2); sym_root.right = TreeNode(2)
sym_root.left.left = TreeNode(3); sym_root.left.right = TreeNode(4)
sym_root.right.left = TreeNode(4); sym_root.right.right = TreeNode(3)
asym_root = TreeNode(1)
asym_root.left = TreeNode(2); asym_root.right = TreeNode(2)
asym_root.left.right = TreeNode(3); asym_root.right.right = TreeNode(3)
print(is_symmetric(sym_root)) # True
print(is_symmetric(asym_root)) # False
Output:
True
False
Tree traversal is not just an academic exercise. In-order extracts sorted data. Pre-order serializes trees. Post-order evaluates and cleans up. Level-order finds shortest paths and processes level by level. Every traversal has its natural use case, and every traversal can be done both recursively (clean, intuitive) and iteratively (explicit stack or queue, avoids recursion limit). Knowing which traversal to reach for is one of the most valuable instincts in coding interviews and real-world development.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises