The basic structure of a tree is a very important concept in data structures, consisting of nodes and edges. Each node can have multiple child nodes (subtrees), but only one parent node (except the root node). For example, in a family tree, the topmost “grandfather” is the root, his sons are first-level child nodes, and his grandchildren are second-level child nodes, until the “leaf” nodes with no children.
What is DFS?¶
DFS (Depth-First Search, Depth-First Search) is a traversal or search method. Its core idea is “Go all the way down a path until you can’t, then backtrack”. Imagine exploring a maze: you choose a path and go forward until you can’t proceed (e.g., hit a dead end), then return to the fork and choose the next path. This “go deep first, then backtrack” approach is the hallmark of DFS.
Classification of Tree DFS Traversals¶
In trees, DFS traversals are typically divided into three types: Pre-order Traversal (Root → Left → Right), In-order Traversal (Left → Root → Right), and Post-order Traversal (Left → Right → Root). Among them, Pre-order Traversal (Root → Left → Right) most directly reflects the “root-to-leaf” path, as it first visits the current node (root), then recursively processes the left subtree, and finally the right subtree—exactly covering the complete path from the root to each leaf.
Recursive Implementation of Pre-order Traversal (Root-to-Leaf Path)¶
Recursion is an intuitive way to implement DFS because it naturally aligns with the logic of “descending into subtrees”. The steps for recursive pre-order traversal are:
1. Visit the current node: Process the current node first (e.g., print its value);
2. Recursively process the left subtree: If there is a left child, recursively perform pre-order traversal on it;
3. Recursively process the right subtree: If there is a right child, recursively perform pre-order traversal on it.
Example: Consider a simple binary tree (root is 1, left child 2, right child 3; 2 has left child 4 and right child 5):
1
/ \
2 3
/ \
4 5
Recursion Process:
- Visit 1 → Recurse left subtree 2 → Visit 2 → Recurse left subtree 4 → Visit 4 (no left/right children, return) → Recurse right subtree 5 → Visit 5 (no left/right children, return) → Recurse right subtree 3 → Visit 3 (no left/right children, return).
- Final visit order: 1 → 2 → 4 → 5 → 3.
Pseudocode (Python-style):
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def dfs_preorder(node):
if node is None: # Return immediately for empty nodes
return
print(node.val, end=" ") # Visit current node
dfs_preorder(node.left) # Recurse on left subtree
dfs_preorder(node.right) # Recurse on right subtree
# Construct the example tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# Call the function to output the root-to-leaf path
dfs_preorder(root) # Output: 1 2 4 5 3
Non-Recursive Pre-order Traversal (Using Stack)¶
Recursion involves self-function calls, but DFS’s “depth-first” can also be simulated with a stack (a “Last-In-First-Out” data structure). The steps for non-recursive pre-order traversal are:
1. Initialize the stack: Push the root node onto the stack;
2. Loop to process the top of the stack:
- Pop the top node and visit it;
- Push right child first, then left child (since the stack is LIFO, pushing the right subtree first ensures the left subtree is processed first);
3. Termination condition: The traversal ends when the stack is empty.
Pseudocode (Python-style):
def dfs_preorder_iterative(root):
if root is None:
return
stack = [root] # Initialize stack with root node
while stack:
node = stack.pop() # Pop the top node
print(node.val, end=" ") # Visit the node
# Push right first, then left to ensure left is processed next
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# Call the function to output the result (same as above)
dfs_preorder_iterative(root) # Output: 1 2 4 5 3
Why is Root-to-Leaf Traversal Important?¶
Root-to-leaf DFS traversal is foundational for solving “path-related problems”, such as:
- Path Sum: Check if the sum of all root-to-leaf paths equals a target value;
- Path Output: Print all root-to-leaf paths (e.g., 1→2→4, 1→2→5, 1→3 in the example);
- Shortest Path: In weighted trees, find the minimum/maximum path sum from root to leaf.
Summary¶
The core of DFS (Depth-First Search) is “exploring one path deeply until you can’t proceed, then backtracking”. Pre-order traversal of a tree is a typical root-to-leaf path traversal. The recursive implementation is simple and intuitive, ideal for beginners to understand; the non-recursive implementation uses a stack to simulate the recursion process, making it more suitable for handling large-scale data. Mastering root-to-leaf DFS traversal helps solve path-related algorithmic problems and is a core skill in the “Tree” chapter of data structures.