In-Order, Pre-Order, Post-Order DFS
Implement all three DFS traversals recursively and iteratively with an explicit stack, explaining when each order is useful.
In-Order, Pre-Order, Post-Order DFS is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Three DFS Traversal Orders
DFS on a binary tree visits nodes in one of three orders based on when the root is processed relative to its children. Pre-order: root → left → right. In-order: left → root → right. Post-order: left → right → root. The names tell you where the root goes in the sequence. Understanding all three is essential because different problems require different orders.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Recursive Pre-Order Traversal
In pre-order, the current node is processed before its subtrees. This mirrors the natural top-down reading of a tree and is used for tree copying, serialisation, and prefix-expression evaluation. The recursive implementation is trivially short but builds a call stack of depth O(h) where h is the tree height.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Recursive In-Order Traversal
In-order traversal visits the left subtree, then the root, then the right subtree. For a Binary Search Tree, in-order traversal always produces a sorted sequence — this property is used by problems like validate BST, kth-smallest element, and BST to sorted array. It is the single most important traversal to know for BST problems.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Recursive Post-Order Traversal
Post-order traversal processes both children before the current node. This bottom-up order is natural when the parent's computation depends on its children's results — for example, computing subtree sizes, deleting a tree, or evaluating an expression tree. Most tree problems that pass information upward use implicit post-order logic.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Iterative Pre-Order with a Stack
To avoid recursion-depth limits, implement DFS iteratively using an explicit stack. For pre-order: push the root, then in each iteration pop a node, record it, and push its right child then left child (right first so left is processed first). This mimics the call stack's LIFO behaviour and is the go-to approach for deep trees where Python's default recursion limit of 1000 would fail.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Iterative In-Order with a Stack
Iterative in-order is slightly trickier. Use a stack and a pointer curr: go left as far as possible, pushing every node. When you can't go further left, pop, record the node, then move right. This pattern — push left until null, pop and process, then go right — is a staple iterative technique that appears in BST iterator problems.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]Iterative Post-Order with Two Stacks
Iterative post-order has a neat trick: run a modified pre-order (root → right → left) and collect results in reverse. Push root, pop and add to front of result, push left then right. The reversal converts root-right-left into left-right-root — which is exactly post-order. Alternatively use a prev pointer to track the last-visited node with a single stack.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]When to Choose Which Traversal
Choosing the right traversal is a key interview signal. Use pre-order when you need to process a parent before its children (serialise tree, copy structure). Use in-order for BSTs to leverage sorted ordering. Use post-order when computing values that depend on both children (height, diameter, subtree sum). BFS is preferred for shortest-path and level-grouping problems.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Morris Traversal: O(1) Space In-Order
Morris traversal achieves O(1) space in-order by temporarily modifying the tree. For each node with a left subtree, find the in-order predecessor (rightmost node of the left subtree) and link its right pointer back to the current node. After visiting, restore the link. This advanced technique is asked in top-tier interviews when the interviewer says 'can you do it with O(1) extra space?'
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Reconstruct Tree from Traversals
Given pre-order and in-order arrays, you can reconstruct the original tree. The first element of pre-order is always the root. Find that root in the in-order array — everything to its left belongs to the left subtree, everything to the right to the right subtree. Recursively apply this to the sub-arrays. Time complexity is O(n) with a hash-map index lookup.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Traversal Time and Space Summary
All three DFS traversals have O(n) time complexity because every node is visited exactly once. Space complexity is O(h) where h is the tree height — O(log n) for balanced trees and O(n) for skewed trees (due to the call stack or explicit stack). Iterative implementations avoid Python's recursion limit but use the same asymptotic space. Morris traversal uniquely achieves O(1) space by reusing the tree's right pointers.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: three DFS traversal orders (pre, in, post) and when to choose each, recursive and iterative implementations using an explicit stack, and the Morris O(1) space technique. Next up we explore computing diameter, height, and balance of binary trees.
Frequently asked questions
Is the “In-Order, Pre-Order, Post-Order DFS” lesson free?
Yes — the full text of “In-Order, Pre-Order, Post-Order DFS” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “In-Order, Pre-Order, Post-Order DFS”?
Implement all three DFS traversals recursively and iteratively with an explicit stack, explaining when each order is useful. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “In-Order, Pre-Order, Post-Order DFS” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- TreeNode Class and Level-Order BFS
- In-Order, Pre-Order, Post-Order DFS
- Diameter, Height, and Balanced Trees
- Path Sum and Lowest Common Ancestor