DSA Interview Prep · Lesson

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.

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]

All lessons in this course

← Back to DSA Interview Prep