Depth-First Search (DFS) for Trees

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

Interactive DFS Traversal Visualization

The visualization below demonstrates the DFS traversal process on a sample tree. You can see how the algorithm explores each branch to its depth before backtracking.

DFS Traversal (Tree)

Step 1 of 0

Action

Ready to start

Current Node

None

Stack

[]

Traversal Order

[]

Current Node

Visited

In Stack

Unvisited

Depth-First Search (DFS) Algorithm

Depth-First Search (DFS) is a tree and graph traversal algorithm that explores as far as possible along each branch before backtracking. For trees, the three main DFS traversals are pre-order, in-order, and post-order.

General Algorithm Steps (Recursive)

Start at the root node.
Process the current node (the timing of this step defines the traversal type: pre-order, in-order, or post-order).
Recursively call DFS on the left child.
Recursively call DFS on the right child.
The base case for the recursion is when a node is null.

Recursive DFS Traversal


# Generic DFS structure (pre-order example)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        def traverse(node):
            if not node:
                return
            # Pre-order: process node, then go left, then right
            res.append(node.val)
            traverse(node.left)
            traverse(node.right)
            
        traverse(root)
        return res

Iterative DFS Traversal

The iterative approach for DFS uses a stack to manage the nodes to visit. This is essentially what the call stack does in the recursive version.

Algorithm Steps

Initialization: Create an empty stack and push the root node onto it.
Loop: While the stack is not empty, do the following:
Pop a node from the stack and process it.
Push the right child onto the stack if it exists.
Push the left child onto the stack if it exists.

Iterative DFS Traversal


# Iterative DFS structure (pre-order example)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs_iterative(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        stack, res = [root], []
        
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
                
        return res