DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Maximum Depth of a Binary Tree

#algorithms #computerscience #interview #leetcode

Problem Statement

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

The maximum depth is the number of nodes along the longest path from the root down to the farthest leaf node.

Brute Force Intuition

In an interview, you can explain it like this:

Traverse every root-to-leaf path, calculate its length, and keep track of the maximum length found.

This works because the deepest root-to-leaf path represents the height of the tree.

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(H)

Moving Towards the Optimal Approach

Observe that the depth of a node depends only on:

Depth of Left Subtree

↓

Depth of Right Subtree
Enter fullscreen mode Exit fullscreen mode

If we already know these two values,

the answer for the current node is simply:

1 + Maximum of Both
Enter fullscreen mode Exit fullscreen mode

This naturally leads to a recursive solution.

Pattern Recognition

Whenever you see:

  • Height of Tree
  • Maximum Depth
  • Longest Root-to-Leaf Path

Think:

DFS + Recursion

Key Observation

For every node:

Height

=

1

+

max(

Left Height,

Right Height

)
Enter fullscreen mode Exit fullscreen mode

Base Case:

NULL

↓

Height = 0
Enter fullscreen mode Exit fullscreen mode

Optimal Approach

Step 1

Recursively calculate:

Left Height
Enter fullscreen mode Exit fullscreen mode

Step 2

Recursively calculate:

Right Height
Enter fullscreen mode Exit fullscreen mode

Step 3

Return:

1 + Math.max(leftHeight, rightHeight);
Enter fullscreen mode Exit fullscreen mode

Optimal Java Solution 

class Solution {

    public int maxDepth(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = maxDepth(root.left);

        int rightHeight = maxDepth(root.right);

        return 1 + Math.max(leftHeight,
                            rightHeight);
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run 

          3
         / \
        9  20
          /  \
         15   7
Enter fullscreen mode Exit fullscreen mode

Node 9 

Left = 0

Right = 0

Height = 1
Enter fullscreen mode Exit fullscreen mode

Node 20 

Left = 1

Right = 1

Height = 2
Enter fullscreen mode Exit fullscreen mode

Root 3 

Left = 1

Right = 2

Height =

1 + max(1,2)

=

3
Enter fullscreen mode Exit fullscreen mode

Final Answer:

3
Enter fullscreen mode Exit fullscreen mode

Why DFS Works?

The height of every node depends only on the heights of its children.

DFS computes the answer from the bottom up.

Leaf nodes return:

1
Enter fullscreen mode Exit fullscreen mode

and each parent builds its height using its children's heights.

Complexity Analysis

Metric Complexity
Time Complexity O(N)
Space Complexity O(H)

Where:

  • N = Number of Nodes
  • H = Height of the Tree

Interview One-Liner

Use DFS to recursively compute the heights of the left and right subtrees, then return one plus the maximum of both.

Pattern Learned 

DFS

↓

Left Height

↓

Right Height

↓

1 + Maximum
Enter fullscreen mode Exit fullscreen mode

Similar Problems

  • Maximum Depth of Binary Tree
  • Minimum Depth of Binary Tree
  • Diameter of Binary Tree
  • Balanced Binary Tree
  • Height of Binary Tree

Memory Trick

Think:

Go Left

↓

Go Right

↓

Take Maximum

↓

Add One
Enter fullscreen mode Exit fullscreen mode

Mental Model 

Leaf

↓

Returns 1

↓

Parent

↓

1 + max(Left, Right)

↓

Root
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Maximum Depth" or "Height of Binary Tree"

your brain should immediately think:

DFS + 1 + max(Left, Right)

Top comments (0)