1. Overview
Depth-First Search (DFS) is a graph traversal algorithm whose core idea is to search as deeply as possible along a path until it can no longer proceed, at which point it backtracks to the previous node and chooses another unexplored path to continue searching.
When choosing another unexplored path to continue searching, it similarly searches as deeply as possible along that path until it can no longer proceed, then backtracks to the previous node and selects another unexplored path to continue searching.
This process is akin to an old monk telling a story to a young monk, representing a classic recursive problem.
Recall the preorder, inorder, and postorder traversal processes of a binary tree; aren’t they also recursive problems?
C++ Programming for Kids (22) Binary Trees
2. Recursion and Binary Tree Traversal
Since DFS relies on recursion, let’s first review the recursive algorithm.
C++ Programming for Kids (14) Recursive Algorithms
There are two key factors in recursion:
- Termination condition (defining boundaries)
- Subproblems (recursive formula)
Recursive Traversal of a Full Binary Tree
For a full binary tree (or complete binary tree), the index of the root node and leaf nodes satisfies the following rules:
- The left child of the parent node k is:2k
- The right child of the parent node k is:2k + 1
- The parent node of the child node k is:k / 2
Note: The index of the root node should start from 1.
Binary Tree Traversal – Code Framework
void dfs(int k) {
if (k >= (1 << n)) return; // Termination condition
// TODO_1 Preorder traversal
dfs(2 * k); // Visit left child
// TODO_2 Inorder traversal
dfs(2 * k + 1); // Visit right child
// TODO_3 Postorder traversal
}
- When node k is greater than or equal to 2^n, the traversal ends. (n is the number of levels in the binary tree)
- dfs(k) traverses node k, dfs(2 * k) traverses the left child, dfs(2*k+1) traverses the right child.
- To perform preorder traversal, simply write the processing code in the TODO_1 position; for inorder traversal, write the processing code in the TODO_2 position; for postorder traversal, write the processing code in the TODO_3 position.
During recursive execution, the operating system creates a stack in memory (system stack), pushing functions onto the stack during function calls and popping them off when the function execution is complete.
The above is a diagram illustrating the process of pushing and popping the system stack based on the binary tree traversal code framework. Referring to the diagram, let’s revisit the calling process of the recursive function.
Complete the binary tree traversal code framework to output the above binary tree in an inorder traversal manner.
3. Classic Cases of DFS
Example 1: Ball Drop
[Problem Description]
A sufficient number of balls drop one by one from a full binary tree FBT (Full Binary Tree), with each ball starting from the root node. During the drop, it either goes to the left subtree or the right subtree, eventually landing on a leaf node. The direction of movement is determined by the boolean value of each node, with all nodes initialized to <span>false</span>.
When a ball lands on a node, if the boolean value of that node is <span>false</span>, the ball changes it to <span>true</span> and then drops to the left subtree; if the boolean value of that node is <span>true</span>, the ball changes it to <span>false</span> and then drops to the right subtree.
Given the number of levels L of the FBT and the number of balls N, write a program to calculate which leaf node the N-th ball lands on.
[Rules Example]
- The first ball drops from node 1, passing through nodes 2 and 4, changing the boolean values of the nodes, and finally landing on node 8.
- The second ball drops from node 1, passing through nodes 3 and 6, changing the boolean values of the nodes, and finally landing on node 12.
- The third ball drops from node 1, passing through nodes 2 and 5, changing the boolean values of the nodes, and finally landing on node 10.
[Input Format]
Input a line containing two numbers: the number of levels L of the FBT and the number of balls N. (2≤L≤16, 1≤N≤1024)
[Output Format]
Output the index of the leaf node where the N-th ball stops falling.
[Sample Input]
4 2
[Sample Output]
12
* Observation and Reflection *
(1) Compare the ball drop with binary tree traversal; what are the similarities and differences?
(2) Does the process of a single ball dropping meet the conditions for recursion?
(3) What data structure should be used to store the node index and boolean value?
Example 1: Ball Drop (Sample Program)
#include <bits/stdc++.h>
using namespace std;
int L, N, ans; // ans stores the result
bool a[1 << 16] = {false}; // Array index represents node index, value represents node value
void dfs(int idx) { // Handling the case when the ball drops to the idx-th node
if (idx >= (1 << (L-1))) { // (Termination condition)
ans = idx; // If the ball drops to a leaf node, save the leaf node index
return; // And return (the ball drop ends)
}
if (a[idx]) { // If the boolean value of the current node is true
a[idx] = false; // Change the boolean value of this node (subproblem)
dfs(2 * idx + 1); // Drop to the right subtree
} else {
a[idx] = true; // Otherwise, change the boolean value of the node (subproblem)
dfs(2 * idx); // Drop to the left subtree
}
}
int main() {
cin >> L >> N; // Input levels L, number of balls N
for(int i = 0; i < N; i++) { // Repeat N times (N balls drop)
dfs(1); // Each ball starts dropping from node 1
}
cout << ans << endl; // Output the index of the last ball's landing leaf node
return 0;
}
The above example is a classic case of depth-first search, which is essentially a recursive problem.
The key to recursion is to handle the boundary problem (termination condition) and the subproblem (recursive formula) correctly.
The termination condition here is the judgment of the leaf node, and the index of the leaf node in a full binary tree should be greater than the sum of the number of nodes in the previous layers; the subproblem is to choose the direction and then drop to the next node, where we only need to consider the root node and its left and right children, and once these three nodes are handled, the subproblem is also resolved.
Example 2: Elimination Tournament
[Problem Description]
There are 2^n students participating in a Go competition. Each student’s strength value is known and all are different. When a student with a higher strength competes against a student with a lower strength, the stronger one wins. Student 1 competes against student 2, the winner advances; student 3 competes against student 4, the winner advances… The students who advance continue to compete in the same way until a champion is determined. Given the strength values of each student, which student is the runner-up?
[Input Format]
The first line inputs an integer n, representing 2^n students. (2≤n≤7)
The second line inputs the strength values of these 2^n students.
[Output Format]
Output a line, an integer representing which student is the runner-up.
[Sample Input]
3
4 2 3 1 10 5 9 7
[Sample Output]
1
* Observation and Reflection *
(1) Is the runner-up the student with the second highest strength value? Why?
(2) Does the elimination tournament satisfy the conditions for recursion? What are the termination condition and subproblem?
(3) What data should be stored for the students? What data structure should be used to store the data?
Draw the competition advancement process; is it similar to a binary tree?
Unlike the previous question, here we only know the strength values and student indices of all leaf nodes, so we need to recursively calculate the strength values and indices of each node above the leaf nodes, and finally access the left and right children of the root node.
However, both the student indices and strength values are mismatched with the node indices, so we cannot use a full binary tree; instead, we will use two binary trees: one to store strength values and the other to store indices.
Example 2: Elimination Tournament (Sample Program)
#include <bits/stdc++.h>
using namespace std;
int n; // n is the number of layers - 1 (indicating there are 2^n students)
int shi_li[1 << (7+1)]; // Array for storing student strength values (bitwise operations have lower precedence than arithmetic operations)
int xu_hao[1 << (7+1)]; // Array for storing student indices
void dfs(int idx){ // Handling the strength value and index of the student at idx-th node
if(idx >= (1 << n)) return; // Termination condition (stop recursion when reaching leaf nodes)
dfs(2 * idx); // Calculate left subtree
dfs(2 * idx + 1); // Calculate right subtree
int sl_l = shi_li[2*idx]; // Get the strength value of the left child
int sl_r = shi_li[2*idx+1]; // Get the strength value of the right child
if(sl_l > sl_r){ // If the left child's strength value is greater than the right child's strength value
shi_li[idx] = sl_l; // Set the strength value of this node to the left child's strength value
xu_hao[idx] = xu_hao[2*idx]; // The left child's student (index) advances
} else { // Otherwise
shi_li[idx] = sl_r; // Set the strength value of this node to the right child's strength value
xu_hao[idx] = xu_hao[2*idx+1]; // The right child's student (index) advances
}
}
int main(){
cin >> n;
for(int i = 0; i < (1 << n); i++){ // Input strength values for 2^n students
cin >> shi_li[(1 << n)+i]; // Store all student strength values as leaf nodes in the strength value array
xu_hao[(1 << n)+i] = i + 1; // Store all student indices as leaf nodes in the index array
}
dfs(1); // Execute the recursive function (DFS)
// If the strength value of node 2 is greater than that of node 3, return the index of node 3; otherwise, return the index of node 2
int ans = (shi_li[2] > shi_li[3] ? xu_hao[3] : xu_hao[2]);
cout << ans << endl; // Output the student number who is the runner-up
return 0;
}
Since we only know the strength values and indices of the leaf nodes, we need to use postorder traversal when traversing the binary tree, because to obtain the value of the parent node, we need to know the values of the left and right child nodes.
Example 3: FBI Tree
String Classification: Strings composed of “0” and “1” can be classified into three categories: a string of all “0” is called a B string, a string of all “1” is called an I string, and a string containing both “0” and “1” is called an F string.
FBI tree is a type of binary tree, and its node types include F nodes, B nodes, and I nodes.
[Problem Description]
From a string of length 2^N composed of <span>0 1</span>, a FBI tree <span>T</span> can be constructed. The recursive construction process is as follows:
- The root node R of T has the same type as the string S;
- If the length of string S is greater than 1, split string S into two equal-length left and right substrings S1 and S2;
- Construct the left subtree T1 of R from substring S1 and the right subtree T2 of R from substring S2.
Now given a string of length 2^N, please construct an FBI tree using the above method and output its postorder traversal sequence.
[Input Format]
The first line inputs an integer N. (0≤N≤10)
The second line inputs a string of length 2^N.
[Output Format]
Output a line, a string representing the postorder traversal sequence of the FBI tree.
[Sample Input]
3
10000111
[Sample Output]
IBFBBBFBIFIIIFF
[Data Scale]
For 40% of the data, N≤3; for 100% of the data, N≤10.
* Observation and Reflection *
Compare this problem with the previous one; are they the same?
Example 3: FBI Tree (Sample Program)
#include <bits/stdc++.h>
using namespace std;
int N;
char T[1 << 11]; // Declare character array T to store the binary tree
void dfs(int x){ // Declare dfs function to recursively traverse the binary tree
if(x >= (1 << N)){ // Stop recursion when reaching leaf nodes
if(T[x] == '1') T[x] = 'I';
else T[x] = 'B'; // Set the leaf node's B, I value
cout << T[x]; // Output the leaf node value
return;
}
dfs(2 * x); // Recursively traverse the left subtree
dfs(2 * x + 1); // Recursively traverse the right subtree
char L = T[2*x]; // Get the left leaf node of the current node
char R = T[2*x+1]; // Get the right leaf node of the current node
if(L == R) // If the left and right leaf nodes are the same
T[x] = L; // Set the current node's value to the left (or right) leaf node value
else // Otherwise
T[x] = 'F'; // Set the current node's value to 'F'
cout << T[x]; // Output the current node value
}
int main(){
cin >> N;
// There are 2^N leaf nodes, indicating that the full binary tree has N+1 layers
for(int i = 1 << N; i < 1 << (N + 1); i++)
cin >> T[i]; // Input the values of the leaf nodes
dfs(1); // Start traversing from node 1
return 0;
}
Example 4: Depth of a Binary Tree
[Problem Description]
Given the two child nodes of each node, construct a binary tree (with the root node as 1). If it is a leaf node, input <span>0 0</span>. After constructing the binary tree, we want to know the depth of this binary tree. The depth of a binary tree refers to the maximum number of layers traversed from the root node to the leaf node. (Depth and layers are the same)
[Input Format]
Input n+1 lines. The first line inputs an integer n, indicating the number of nodes. (0≤N≤1e6)
The next n lines input two natural numbers for each node number, representing the left and right child nodes.
[Output Format]
Output a line, an integer representing the depth of the binary tree.
[Sample Input]
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
[Sample Output]
4
* Observation and Reflection *
(1) Draw a diagram and think about what the termination condition and subproblem are?
(2) Consider how to calculate the depth of the binary tree?
Example 4: Depth of a Binary Tree (Sample Program)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 1; // Declare constant to store the maximum number of nodes
int n; // Given number of nodes
int deep = 0; // Depth of the binary tree (default depth is 0)
struct Node{ // Declare struct Node (node)
int left; // Struct contains left and right child nodes
int right;
};
Node node[MAX_N]; // Declare an array of Node type to store nodes
// Declare function to calculate the depth of the binary tree (f is the current node number, d is the current node's depth)
void dfs(int f, int d){
if(f == 0) return; // Stop recursion when the parent node is 0
deep = max(deep, d); // Compare maximum depth
dfs(node[f].left, d + 1); // Traverse left subtree
dfs(node[f].right, d + 1); // Traverse right subtree
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){ // Repeat n times
cin >> node[i].left >> node[i].right; // Input left and right nodes
}
dfs(1, 1); // Execute recursive call
cout << deep << endl; // Output depth
return 0;
}
If we do not use structures, will it be more complicated, or is it simpler?
Example 5: Postorder Traversal
[Problem Description]
Input the preorder and inorder traversal sequences of a binary tree, and output its postorder traversal sequence.
[Input Format]
Input two lines. The first line is a string representing the preorder traversal sequence.
The second line is a string representing the inorder traversal sequence.
[Output Format]
Output a line, a string representing the postorder traversal sequence of the binary tree.
[Sample Input]
ABDEC
DBEAC
[Sample Output]
DEBCA
* Observation and Reflection *
(1) Recall the process of manually solving the postorder traversal sequence.
(2) Consider how to programmatically solve the postorder traversal sequence?
Example 5: Postorder Traversal (Sample Program)
#include <bits/stdc++.h>
using namespace std;
// Output postorder traversal sequence based on preorder and inorder traversal sequences (a is the preorder sequence, b is the inorder sequence)
void dfs(string a, string b){
if(a.size() == 0) return; // Stop recursion when the length of the preorder sequence is 0
int index = b.find(a[0]); // Get the index of the root node in the inorder traversal
dfs(a.substr(1, index), b.substr(0, index)); // Recursively traverse the left subtree
dfs(a.substr(index+1), b.substr(index+1)); // Recursively traverse the right subtree
cout << a[0]; // Finally output the root node
}
int main(){
string a, b; // a and b represent the preorder and inorder traversal sequences
cin >> a >> b;
dfs(a, b);
return 0;
}
Example 6: Preorder Traversal
[Problem Description]
Both trees and binary trees have various traversal orders such as preorder, inorder, postorder, and level order. Given the inorder and another traversal sequence, one can determine the structure of a binary tree. Assuming each node of a binary tree is described by a character, now given the inorder and level order strings, find the preorder traversal string of that tree.
[Input Format]
Input a total of two lines, each line is a string composed of uppercase letters (each character is unique), representing the inorder and level order sequences.
[Output Format]
Output a line representing the preorder sequence of the binary tree.
[Sample Input]
DBEAC
ABCDE
[Sample Output]
ABDEC
* Observation and Reflection *
(1) After observation, it is found that the character that appears first in the level order is the root node in the inorder traversal. The root node in the inorder traversal divides the sequence into two segments (i.e., left subsequence and right subsequence), and then recursively calculate the left and right subsequences.
(2) Consider how to quickly find the first character that appears in the inorder sequence in the level order sequence (i.e., the root node). Can we create a mapping of each character in the level order sequence to its order of appearance? If so, how can we do it?
Example 6: Preorder Traversal (Sample Program)
#include <bits/stdc++.h>
using namespace std;
string s1, s2; // s1 is the inorder sequence, s2 is the level order sequence
int char_map[27] = {0}; // Mapping table for characters and their order of appearance
void dfs(string s){ // Declare recursive function to output sequence in preorder traversal
if(s.size() == 0) return; // Termination condition (when the string is empty)
// Traverse the inorder string to find the character that appears first in the level order (the root node)
int cx = 27; // Set the order of the first character to the maximum value (at most 26 uppercase letters)
int idx = -1; // Set the index of the first character to -1 (indicating it does not exist)
for(int i = 0; i < s.size(); i++){
int n = char_map[s[i] - 'A']; // The order of appearance of the i-th character
if(n < cx){
cx = n; // Record the order of the first character
idx = i; // Record the index of the first character
}
}
cout << s[idx]; // Output the root node (the character corresponding to index idx)
dfs(s.substr(0, idx)); // Recursively traverse the left subtree (the string before idx)
dfs(s.substr(idx+1)); // Finally recursively traverse the right subtree (the string after idx)
}
int main(){
cin >> s1 >> s2;
for(int i = 0; i < s1.size(); i++){
char_map[s2[i] - 'A'] = i; // Store the order of appearance for each character
}
dfs(s1); // Call the recursive function (execute depth-first search strategy)
return 0;
}
Summary
The implementation of DFS typically relies on recursion (using function calls and the system stack to achieve backtracking) or a stack (manually maintaining search state), and is suitable for solving problems such as path searching, connectivity checking, and topological sorting.
< This lesson ends here >
Previous Recommendations
C++ Programming for Kids (Supplement 1) Original Code, Inverse Code, and Complement Code
C++ Programming for Kids (23) Basics of Graph Theory
C++ Programming for Kids (22) Binary Trees
C++ Programming for Kids (21) Stacks and Queues
C++ Programming for Kids (20) Prefix Sums and Differences
Scan the QR code to get
More exciting content
Little Xiaoshan Programming for Kids
