Maximum Depth of Binary Tree easy

Problem Statement

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.

Example 1

Input: root = [3,9,20,null,null,15,7] Output: 3

Example 2

Input: root = [1,null,2] Output: 2

Steps

  1. Base Case: If the root is null (empty tree), the maximum depth is 0.
  2. Recursive Step: Recursively calculate the maximum depth of the left and right subtrees.
  3. Maximum Depth: The maximum depth of the entire tree is 1 (for the root) plus the maximum of the depths of the left and right subtrees.

Explanation

The solution uses a depth-first search (DFS) approach employing recursion. The function maxDepth explores the tree level by level. For each node, it recursively calls itself on the left and right children. The maximum depth is found by taking the maximum depth of the left and right subtrees and adding 1 (to account for the current node). The base case handles the scenario where a subtree is empty (null), returning a depth of 0.

Code

/**
 * 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) {
        // Base case: empty tree
        if (root == nullptr) {
            return 0;
        } else {
            // Recursive step: calculate depth of left and right subtrees
            int leftDepth = maxDepth(root->left);
            int rightDepth = maxDepth(root->right);

            // Maximum depth is 1 + max(leftDepth, rightDepth)
            return 1 + max(leftDepth, rightDepth);
        }
    }
};

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In the best case (a balanced tree), H would be logâ‚‚(N).