A binary tree is one of the important data structures in computer science,
where each node has at most two child nodes.
Binary trees are used for various purposes such as searching, sorting, and data storage,
and frequently appear in algorithm problems.
In this lecture, we will solve algorithm problems utilizing binary trees.
Problem: Finding the Maximum Depth of a Binary Tree
The problem is to traverse a given binary tree and calculate its depth.
The maximum depth refers to the length of the path from the root node to the deepest leaf node.
If the binary tree is empty, the depth is 0.
The following are the input and output formats.
Input Format
The binary tree is given in the form of an array, and each node is defined as follows:
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
Output Format
Returns the maximum depth of the binary tree as an integer.
Example
Input: [3,9,20,null,null,15,7]
Output: 3
Problem Solving Approach
To solve this problem, a method to traverse the binary tree is required.
We can mainly traverse in two ways:
depth-first search (DFS) or breadth-first search (BFS).
In this case, we will choose to use DFS to recursively traverse the tree.
Depth-First Search – Recursive Method
Through recursion, we visit each node of the tree and
continuously call the left and right child nodes to check the depth.
Below is the core idea of the algorithm representing this process.
- If the current node is NULL, return 0.
- Recursively call the left subtree to obtain its depth.
- Recursively call the right subtree to obtain its depth.
- Select the greater of the left and right depths and add 1 before returning.
Implementation
Now, let’s implement the above-described algorithm in C++ code.
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
};
Code Explanation
The above code is a function written in C++ that calculates the maximum depth of a binary tree.
The maxDepth function is called recursively to calculate the
maximum depth of the given node.
- In
if (root == NULL), we check if the node is NULL. If it is NULL, the depth is 0, so we return it. - Calculate the depths for the left and right children and choose the larger value before adding 1.
- The final returned value is the overall maximum depth.
Testing
Now, let’s verify the functionality of the algorithm through some test cases.
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
Solution solution;
int result = solution.maxDepth(root);
cout << result; // 3
Conclusion
We examined how to implement an algorithm that calculates the maximum depth of
a binary tree in C++.
Through this problem, we were able to learn the basics of recursive traversal,
which will serve as a foundation for solving more complex tree-related problems.
I hope you will continue to study binary trees in depth.
Thank you!