104. Maximum Depth of Binary Tree - Solution

Q: Is Maximum Depth of Binary Tree easy or hard?

Maximum Depth of Binary Tree is classified as an Easy problem on most coding platforms. It focuses on fundamental tree traversal concepts and is often used to introduce DFS recursion or BFS level-order traversal.

Q: Maximum Depth of Binary Tree Python Java solution

In Python or Java, the typical solution uses recursion: return 0 for a null node, otherwise return 1 plus the maximum depth of the left and right children. BFS solutions use a queue to process nodes level by level and increment the depth after finishing each level.

Q: How to solve Maximum Depth of Binary Tree in O(n)?

Traverse the tree once using either DFS or BFS. With DFS, recursively compute the maximum depth of left and right children and return 1 + max(left, right). With BFS, process nodes level by level using a queue and count the number of levels until the queue becomes empty.

Q: What is the best approach for Maximum Depth of Binary Tree?

Recursive Depth-First Search (DFS) is the most common and clean approach. For each node, compute the depth of the left and right subtrees and return 1 plus the larger value. This visits every node once, giving O(n) time complexity and O(h) space complexity for the recursion stack.

Q: Is Maximum Depth of Binary Tree asked at Google Amazon Meta?

Maximum Depth of Binary Tree is a classic tree traversal problem frequently used in technical interviews. Variants and related tree depth problems have appeared in interviews at companies such as Amazon, Google, Meta, and Microsoft because they test understanding of recursion and tree traversal.

Q: What data structure is used in Maximum Depth of Binary Tree?

The problem uses a binary tree as the primary data structure. Solutions typically rely on recursion with the call stack for DFS or a queue for BFS level-order traversal.

Q: What is the time complexity of Maximum Depth of Binary Tree?

The time complexity is O(n) because every node in the binary tree must be visited at least once to determine the deepest path. Both DFS and BFS implementations process each node exactly once.

The 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.

Example 1:

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

Example 2:

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

Constraints:

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

Approach overview

Problem Overview: Given the root of a binary tree, return its maximum depth. The depth is the number of nodes along the longest path from the root down to a leaf node. You need to traverse the tree and determine how far the deepest branch extends.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

This approach uses recursion to explore the tree using Depth-First Search. For each node, recursively compute the depth of its left and right subtrees. The maximum depth at that node is 1 + max(leftDepth, rightDepth). The recursion naturally mirrors the structure of the binary tree, making the implementation very concise. Time complexity is O(n) because every node is visited once. Space complexity is O(h), where h is the tree height, due to the recursion stack. In the worst case of a skewed tree, this becomes O(n); for balanced trees it is O(log n). This is the most common solution used in interviews.

Approach 2: Breadth-First Search (BFS) using Queue (Time: O(n), Space: O(w))

This method traverses the tree level by level using Breadth-First Search. Start by pushing the root node into a queue. For each level, process all nodes currently in the queue, then push their left and right children. After finishing a level, increment the depth counter. Continue until the queue becomes empty. Since each node is enqueued and dequeued exactly once, the time complexity remains O(n). Space complexity is O(w), where w is the maximum width of the tree (the largest number of nodes at any level). This approach is useful when you want explicit control over level traversal.

Recommended for interviews: Recursive DFS is typically the expected solution because it directly models the recursive structure of a tree and results in very clean code. BFS using a queue demonstrates understanding of level-order traversal and iterative tree processing. Showing both approaches signals strong familiarity with tree traversal patterns.

Approach 1: Recursive Depth-First Search (DFS)

This approach involves using a recursive function that traverses the tree in a depth-first manner. For each node, calculate the maximum depth of its left and right subtrees, and add 1 for the current node itself. The function returns the maximum of these two values. This provides an elegant and intuitive solution, leveraging the inherent recursive structure of trees.

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

Java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

C++

#include <algorithm>
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var maxDepth = function(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

#include <stdio.h>
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

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

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
    }
}

This Python solution verifies if the tree root exists. If not, it returns 0. Otherwise, it recursively calculates the maximum depth of both subtrees, adding 1 to account for the current node.

Complexity

Time Complexity: O(n), with n being the node count.
Space Complexity: O(h), where h is the height of the tree due to recursion stack.

Try this approach in the editor

Approach 2: Breadth-First Search (BFS) using Queue

This approach involves using a queue to perform a Breadth-First Search (BFS) on the tree. By iterating level by level, we increment the depth counter with each level traversed completely.

Python

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    q = deque([root])
    depth = 0
    while q:
        levelSize = len(q)
        for _ in range(levelSize):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        depth += 1
    return depth

Java

import java.util.LinkedList;
import java.util.Queue;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth = 0;
        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.poll();
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            depth++;
        }
        return depth;
    }
}

C++

#include <queue>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int level_size = q.size();
        for (int i = 0; i < level_size; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        depth++;
    }
    return depth;
}

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var maxDepth = function(root) {
    if (!root) return 0;
    let q = [root];
    let depth = 0;
    while (q.length > 0) {
        let levelSize = q.length;
        for (let i = 0; i < levelSize; i++) {
            let node = q.shift();
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
        depth++;
    }
    return depth;
};

#include <stdio.h>
#include <stdlib.h>
#define MAX_Q_SIZE 500

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

TreeNode** createQueue(int* front, int* rear) {
    TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * MAX_Q_SIZE);
    *front = *rear = 0;
    return queue;
}

void enqueue(TreeNode** queue, int* rear, TreeNode* new_node) {
    queue[*rear] = new_node;
    (*rear)++;
}

TreeNode* dequeue(TreeNode** queue, int* front) {
    (*front)++;
    return queue[*front - 1];
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    int depth = 0;
    int front, rear;
    TreeNode** queue = createQueue(&front, &rear);
    enqueue(queue, &rear, root);
    while (front < rear) {
        int count = rear - front;
        for (int i = 0; i < count; i++) {
            TreeNode* node = dequeue(queue, &front);
            if (node->left) enqueue(queue, &rear, node->left);
            if (node->right) enqueue(queue, &rear, node->right);
        }
        depth++;
    }
    free(queue);
    return depth;
}

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        int depth = 0;
        while (q.Count > 0) {
            int levelSize = q.Count;
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.Dequeue();
                if (node.left != null) q.Enqueue(node.left);
                if (node.right != null) q.Enqueue(node.right);
            }
            depth++;
        }
        return depth;
    }
}

Using Python's collections.deque for efficient pops from a queue's left side, each level’s nodes are tracked and processed, incrementing depth post each level traverse.

Complexity

Time Complexity: O(n) iterating all nodes.
Space Complexity: O(n) due to deque storage constraints per level.

Try this approach in the editor

Approach 3: Recursion

Recursively traverse the left and right subtrees, calculate the maximum depth of the left and right subtrees, and then take the maximum value plus 1.

The time complexity is O(n), where n is the number of nodes in the binary tree. Each node is traversed only once in the recursion.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l, r := maxDepth(root.Left), maxDepth(root.Right)
	return 1 + max(l, r)
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if root.is_none() {
            return 0;
        }
        let node = root.as_ref().unwrap().borrow();
        1 + Self::dfs(&node.left).max(Self::dfs(&node.right))
    }

    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(&root)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Depth-First Search (DFS)	Time Complexity: O(n), with n being the node count. Space Complexity: O(h), where h is the height of the tree due to recursion stack.
Breadth-First Search (BFS) using Queue	Time Complexity: O(n) iterating all nodes. Space Complexity: O(n) due to deque storage constraints per level.
Recursion	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Depth-First Search (DFS)	O(n)	O(h)	Best general solution. Clean recursive logic that mirrors tree structure. Preferred in interviews.
Breadth-First Search (BFS) with Queue	O(n)	O(w)	Useful when performing level-order traversal or when recursion depth could be large.

Frequently asked questions

Is Maximum Depth of Binary Tree easy or hard?

Maximum Depth of Binary Tree is classified as an Easy problem on most coding platforms. It focuses on fundamental tree traversal concepts and is often used to introduce DFS recursion or BFS level-order traversal.

Maximum Depth of Binary Tree Python Java solution

In Python or Java, the typical solution uses recursion: return 0 for a null node, otherwise return 1 plus the maximum depth of the left and right children. BFS solutions use a queue to process nodes level by level and increment the depth after finishing each level.

How to solve Maximum Depth of Binary Tree in O(n)?

Traverse the tree once using either DFS or BFS. With DFS, recursively compute the maximum depth of left and right children and return 1 + max(left, right). With BFS, process nodes level by level using a queue and count the number of levels until the queue becomes empty.

What is the best approach for Maximum Depth of Binary Tree?

Recursive Depth-First Search (DFS) is the most common and clean approach. For each node, compute the depth of the left and right subtrees and return 1 plus the larger value. This visits every node once, giving O(n) time complexity and O(h) space complexity for the recursion stack.

Is Maximum Depth of Binary Tree asked at Google Amazon Meta?

Maximum Depth of Binary Tree is a classic tree traversal problem frequently used in technical interviews. Variants and related tree depth problems have appeared in interviews at companies such as Amazon, Google, Meta, and Microsoft because they test understanding of recursion and tree traversal.

What data structure is used in Maximum Depth of Binary Tree?

The problem uses a binary tree as the primary data structure. Solutions typically rely on recursion with the call stack for DFS or a queue for BFS level-order traversal.

What is the time complexity of Maximum Depth of Binary Tree?

The time complexity is O(n) because every node in the binary tree must be visited at least once to determine the deepest path. Both DFS and BFS implementations process each node exactly once.

Maximum Depth of Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search (DFS)

Approach 2: Breadth-First Search (BFS) using Queue

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Depth of Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search (DFS)

Approach 2: Breadth-First Search (BFS) using Queue

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems