Mastering the LCA Algorithm in C++
Tree Traversal Techniques
Depth-First Search
Depth-First Search (DFS) is a traversal algorithm that explores as far as possible along each branch before backtracking. Think of it like navigating a maze. You pick a path and follow it to the very end. If you hit a dead end, you backtrack to the last junction and try an unexplored path. You repeat this until you've explored the entire maze.
In a tree, DFS starts at the root and explores as far as possible down one branch. Once it reaches a leaf node (a dead end), it backtracks to the most recent ancestor with an unvisited child and explores that branch. This process continues until all nodes have been visited. Because of its recursive nature, DFS is often implemented using a stack, either explicitly or implicitly through function calls.
Depth-First Search (DFS) is a traversal algorithm that explores as far as possible along each branch before backtracking.
There are three common ways to perform a DFS traversal: pre-order, in-order, and post-order. For now, we'll focus on a generic DFS implementation that visits each node. This approach is often used as a backbone for more complex algorithms.
#include <iostream>
#include <vector>
// Adjacency list representation of the tree
std::vector<int> adj[100];
// Visited array to keep track of visited nodes
bool visited[100];
void dfs(int u) {
// Mark the current node as visited
visited[u] = true;
std::cout << u << " "; // Process the node
// Recur for all the vertices adjacent to this vertex
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
int main() {
// Example Tree: 1 is the root
// 1 -> 2, 3
// 2 -> 4, 5
// 3 -> 6
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[3].push_back(6);
std::cout << "DFS traversal starting from root 1: ";
dfs(1);
std::cout << std::endl;
return 0;
}
// Output: DFS traversal starting from root 1: 1 2 4 5 3 6
Breadth-First Search
Breadth-First Search (BFS) explores nodes layer by layer. It starts at the root, visits all of the root's direct children, then all of their direct children, and so on. It's like dropping a stone in a pond: the ripples spread out from the center, one circle at a time.
To keep track of nodes to visit, BFS uses a queue. The algorithm starts by adding the root to the queue. Then, it enters a loop: it removes the front node from the queue, processes it, and adds all of its unvisited children to the back of the queue. The loop continues until the queue is empty, ensuring every node has been visited level by level.
BFS is useful for finding the shortest path between two nodes in an unweighted graph or tree, as it always finds the shallowest unvisited node first.
Here is a standard C++ implementation of BFS using a queue.
#include <iostream>
#include <vector>
#include <queue>
// Adjacency list representation of the tree
std::vector<int> adj[100];
// Visited array to keep track of visited nodes
bool visited[100];
void bfs(int start_node) {
// Create a queue for BFS
std::queue<int> q;
// Mark the start node as visited and enqueue it
visited[start_node] = true;
q.push(start_node);
while (!q.empty()) {
// Dequeue a vertex from the front of the queue
int u = q.front();
q.pop();
std::cout << u << " "; // Process the node
// Get all adjacent vertices of the dequeued vertex u.
// If an adjacent has not been visited, then mark it
// visited and enqueue it.
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
int main() {
// Example Tree: 1 is the root
// Using the same tree as the DFS example
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[3].push_back(6);
std::cout << "BFS traversal starting from root 1: ";
bfs(1);
std::cout << std::endl;
return 0;
}
// Output: BFS traversal starting from root 1: 1 2 3 4 5 6
Complexity and Applications
For both DFS and BFS, every node and every edge is visited exactly once. This makes their performance predictable and efficient.
Let be the number of vertices (nodes) and be the number of edges in the tree. In a tree, the number of edges is always one less than the number of vertices, so .
| Traversal | Time Complexity | Space Complexity |
|---|---|---|
| DFS | , where is the height of the tree. | |
| BFS | , where is the maximum width of the tree. |
The time complexity for both is because each vertex and edge is processed once. Since for a tree , this is effectively .
The space complexity differs. For DFS, the space required is determined by the maximum depth of the recursion stack, which is the height of the tree (). For a skewed tree, this can be as bad as . For BFS, the space depends on the maximum number of nodes in the queue at any time, which corresponds to the maximum width of the tree (). In a complete binary tree, the last level can contain about nodes, leading to a worst-case space complexity of .
These traversal methods are fundamental building blocks. DFS is used in topological sorting, finding connected components, and solving puzzles like mazes. BFS is used to find the shortest path in unweighted graphs and in algorithms like Cheney's algorithm for garbage collection.
Let's check your understanding of these core concepts.
Which search algorithm explores a graph layer by layer, similar to ripples spreading in a pond?
What data structure is typically used to implement a Breadth-First Search (BFS) algorithm?
Understanding how to traverse a tree is the first step toward solving more complex problems, such as finding the lowest common ancestor of two nodes.