104. Maximum Depth of Binary Tree

Problem Description

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution

To find the maximum depth of a binary tree, we can use a recursive approach. We define a helper function, maxDepth, that takes in the root node of the tree.

First, we handle the base case where the root is null. In this case, the depth is 0 since there are no nodes in the tree.

If the root is not null, we recursively calculate the maximum depth of the left and right subtrees. We do this by calling maxDepth on the left and right child nodes of the current root.

We then take the maximum of the depths of the left and right subtrees and add 1 to it (to account for the current root node). This gives us the maximum depth of the binary tree.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        } else {
            int left_height = maxDepth(root->left);
            int right_height = maxDepth(root->right);
            return std::max(left_height, right_height) + 1;
        }
    }
}
    

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node once to calculate the maximum depth.

The space complexity is O(h), where h is the height of the binary tree. In the worst case, the tree can be skewed, resulting in a space complexity of O(n). However, in a balanced tree, the space complexity is O(log n).

Example

Consider the following binary tree:

            3
           / \
          9   20
             /  \
            15   7
    

We can use the provided code to find the maximum depth of the tree:

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 maxDepth = solution.maxDepth(root);
    

After executing the code, the value of maxDepth will be 3 since the longest path from the root to a leaf is 3.

Conclusion

In this blog post, we explored the problem of finding the maximum depth of a binary tree. We discussed a recursive solution and provided the corresponding C++ implementation. Additionally, we analyzed the time and space complexities of the solution and demonstrated an example usage of the code.

Feel free to try out the code with different binary trees to find their maximum depths!