Depth-First Search explores as far down a branch as possible before backtracking. Pre-order DFS visits the current node, then the left subtree, then the right subtree. It uses a stack — either the call stack (recursive) or an explicit one (iterative). Space complexity is O(h) where h is the tree height.
Example: Pre-order DFS traversal of a 7-node binary tree.
Depth-First Search dives as deep as possible before backtracking. Pre-order DFS visits the current node first, then recurses into the left subtree, then the right.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
defdfs(node):
2
stack=[node]
3
whilestack:
4
n=stack.pop()
5
print(n.val)
6
ifn.right:stack.append(n.right)
7
ifn.left:stack.append(n.left)
Quick check
What data structure does iterative DFS use?
In pre-order DFS, when is the current node visited relative to its children?