algoadvance

Leetcode 104. Maximum Depth of Binary Tree

Problem Statement

Leetcode Problem 104: Maximum Depth of Binary Tree

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.

Clarifying Questions

  1. Input Constraints:
    • Is it possible for the input tree to be empty?
      • Yes, the input tree can be empty. In such cases, the maximum depth should be 0.
    • Are there any constraints on the number of nodes in the tree?
      • Typically, the number of nodes can go up to (10^4), but we will assume constraints based on typical Leetcode settings unless stated otherwise.
  2. Output:
    • The output should be a single integer indicating the depth of the tree.

Strategy

To determine the maximum depth of a binary tree, we can use Depth First Search (DFS). Specifically, a recursive approach is efficient and intuitive:

  1. Base Case: If the current node is nullptr, return 0.
  2. Recursive Case: The depth of the current node is 1 plus the maximum of the depths of the left and right subtrees.
  3. Recursion: Compute the depth for the left subtree and the right subtree recursively.

Code

Here’s the implementation of the above strategy in C++:

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

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

int main() {
    // Create a sample binary tree:
    //        3
    //       / \
    //      9  20
    //         /  \
    //        15   7
    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;
    std::cout << "Maximum Depth of the binary tree: " << solution.maxDepth(root) << std::endl; // Output: 3
    
    // Clean up memory (optional as main is going to exit, but good for practice)
    delete root->right->right;
    delete root->right->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

Time Complexity

The time complexity of this algorithm is (O(N)), where (N) is the number of nodes in the binary tree. The function visits each node exactly once.

Space Complexity

The space complexity is (O(d)), where (d) is the maximum depth of the tree. This is due to the recursion stack. In the worst-case scenario (a completely unbalanced tree), the depth could be equal to (N). In a balanced tree, the depth would be (O(\log N)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI