Maximum Depth of Binary Tree - Practice Coding Problems

Maximum Depth of Binary Tree - Problem

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.

Input & Output

Example 1 — Balanced Tree

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

› Output: 3

💡 Note: The longest path is from root 3 → 20 → 15 (or 7), which has 3 nodes, so depth is 3.

Example 2 — Linear Tree

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

› Output: 2

💡 Note: The tree has only a right path: 1 → 2, so the depth is 2.

Example 3 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: Tree has only one node (the root), so the depth is 1.

Constraints

The number of nodes in the tree is in the range [0, 10⁴]
-100 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes at different levels

Find Paths

Identify all root-to-leaf paths

Count Levels

Return the maximum number of levels (nodes in longest path)

Key Takeaway

🎯 Key Insight: Tree depth equals 1 + maximum depth of subtrees

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is that the maximum depth equals 1 plus the maximum depth of the left and right subtrees. Best approach is DFS recursion for simplicity or BFS iteration to avoid stack overflow. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Depth-First Search (Recursive)	O(n)	O(h)	Recursively explore left and right subtrees, returning 1 + max depth
Breadth-First Search (Iterative)	O(n)	O(w)	Use a queue to traverse level by level, counting the number of levels

Depth-First Search (Recursive) — Algorithm Steps

Base case: if node is null, return 0
Recursively get left subtree depth
Recursively get right subtree depth
Return 1 + max(left_depth, right_depth)

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Node

At each node, recursively get left and right depths

Combine

Return 1 + max(left_depth, right_depth)

Result

Root returns the maximum depth of entire tree

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int solution(struct TreeNode* root) {
    if (!root) {
        return 0;
    }
    
    int leftDepth = solution(root->left);
    int rightDepth = solution(root->right);
    
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // For simplicity, assume input is [3,9,20,null,null,15,7]
    // Create the tree manually for this example
    struct TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left = createNode(15);
    root->right->right = createNode(7);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once where n is number of nodes

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h, worst case O(n) for skewed tree

✓ Linear Space

235.8K Views

High Frequency

~15 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Depth-First Search (Recursive) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler