Depth-First Search (DFS):
DFS is a traversal technique used to explore nodes of a tree by diving deep into one branch before backing up to explore others. It uses a stack (or recursion) to explore as deep as possible along each branch before backtracking. DFS visits a node, processes it, and then recursively visits all its children.
- Pre-order DFS: Process the current node, then recursively process left and right children.
- In-order DFS: Recursively process the left child, then the current node, and finally the right child.
- Post-order DFS: Recursively process the left and right children, then process the current node.
Breadth-First Search (BFS):
BFS is a traversal technique that explores all nodes at the present depth level before moving to nodes at the next depth level. It uses a queue to explore nodes level by level. BFS is particularly useful for finding the shortest path in an unweighted tree or graph.
Key Concept:
- DFS uses recursion or a stack (LIFO) structure.
- BFS uses a queue (FIFO) structure.
How to Identify This Pattern in a Given Coding Question
These patterns are useful when:
- You need to explore or search through a tree-like structure.
- You are asked to process nodes in a specific order (pre-order, in-order, post-order for DFS).
- You need to explore a tree level by level (BFS).
- Common phrases: “traverse the tree,” “find the path,” “explore all nodes,” “find shortest path,” or “search.”
Example Questions:
Traverse a binary tree (pre-order, in-order, post-order).
- Level order traversal of a binary tree.
- Find the depth or height of a binary tree.
- Find the shortest path in an unweighted tree.
What Are the Variances of It?
Depth-First Search (DFS):
- Pre-order DFS: Visit the root, then the left subtree, then the right subtree.
- In-order DFS: Visit the left subtree, then the root, then the right subtree.
- Post-order DFS: Visit the left subtree, then the right subtree, then the root.
Breadth-First Search (BFS):
- Level-order traversal: Nodes are visited level by level from the root to the leaves.
Other DFS variations:
- Modified DFS: Sometimes you may modify the traversal order for specific tasks, such as path finding, backtracking, or finding connected components in a graph.
Tricks to Keep in Mind
DFS Tricks:
- Recursion Depth: Watch out for deep trees when using recursion; Python has a recursion limit, so be cautious of stack overflow.
- Traversal Variants: Understand when to use pre-order, in-order, and post-order based on the problem’s requirements.
- Backtracking: DFS can be useful when exploring multiple possibilities and reverting to a previous state (e.g., pathfinding, generating permutations).
BFS Tricks:
- Queue for Level-order: Use a queue to traverse the tree level by level, enqueuing child nodes after processing the parent.
- Shortest Path: BFS guarantees the shortest path in an unweighted tree or graph because it explores all nodes at the current depth before moving deeper.
Examples
Example 1: DFS - Pre-order Traversal
from typing import Optional, List
class TreeNode:
def __init__(self, value: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
self.value = value
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root: Optional[TreeNode] = None
def pre_order_dfs(self, node: Optional[TreeNode], result: List[int]) -> None:
"""
Pre-order DFS traversal: Root -> Left -> Right
"""
if not node:
return
result.append(node.value) # Process the current node
self.pre_order_dfs(node.left, result) # Traverse left subtree
self.pre_order_dfs(node.right, result) # Traverse right subtree
# Example usage
bt = BinaryTree()
bt.root = TreeNode(1, TreeNode(2), TreeNode(3))
result: List[int] = []
bt.pre_order_dfs(bt.root, result)
print(result) # Output: [1, 2, 3]
Example 2: DFS - In-order Traversal
from typing import Optional, List
class TreeNode:
def __init__(self, value: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
self.value = value
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root: Optional[TreeNode] = None
def in_order_dfs(self, node: Optional[TreeNode], result: List[int]) -> None:
"""
In-order DFS traversal: Left -> Root -> Right
"""
if not node:
return
self.in_order_dfs(node.left, result) # Traverse left subtree
result.append(node.value) # Process the current node
self.in_order_dfs(node.right, result) # Traverse right subtree
# Example usage
bt = BinaryTree()
bt.root = TreeNode(1, TreeNode(2), TreeNode(3))
result: List[int] = []
bt.in_order_dfs(bt.root, result)
print(result) # Output: [2, 1, 3]
Example 3: BFS - Level-order Traversal
from collections import deque
from typing import Optional, List
class TreeNode:
def __init__(self, value: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
self.value = value
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root: Optional[TreeNode] = None
def bfs_level_order(self) -> List[List[int]]:
"""
BFS level-order traversal. Returns nodes by level.
"""
result = []
if not self.root:
return result
queue = deque([self.root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
# Example usage
bt = BinaryTree()
bt.root = TreeNode(1, TreeNode(2), TreeNode(3))
result = bt.bfs_level_order()
print(result) # Output: [[1], [2, 3]]