Problem

Given a binary tree, find its maximum depth.

Definition

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.

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

Example

Example 1

1
2

Input: root = [1, 2, 3, 4, 5, 5, null, 4]
Output: 4

Example 2

1
2
3
4
5

     1
   /    \
  2      3
 /  \   /  \
4    5 6    7

1
2

Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: 3

Solution

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

Method 1 - Recursive using Post order traversal

This is same as the number of nodes in the longest path. We can see that longest path with just one node is 1 i.e. the node itself. So, height aka max depth aka longest path is one more than the max of left or right sub tree height.

1

height(T) = max{height(T.left), height(T.right)}+1;

Dry Run

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int maxDepth(TreeNode root) {
	if (root == null) {
		return 0;
	}

	int leftDepth = maxDepth(root.left);
	int rightDepth = maxDepth(root.right);

	return 1 + Math.max(leftDepth, rightDepth);
}

Complexity

  • Time Complexity: O(n) where n is number of nodes in tree
  • Space Complexity: O(1)

Method 2 - Iterative Approach Using BFS

We can also use Binary Tree Traversal - Level Order OR BFS to find max depth as well.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public static int maxDepth(Node root) {
	// empty tree has a height of 0
	if (root == null) {
		return 0;
	}
	// create an empty queue and enqueue the root node
	Queue<Node> queue = new ArrayDeque<>();
	queue.add(root);
	Node front = null;
	int height = 0;
	// loop till queue is empty
	while (!queue.isEmpty())
	{
		// calculate the total number of nodes at the current level
		int size = queue.size();
		// process each node of the current level and enqueue their
		// non-empty left and right child
		while (size--> 0)
		{
			front = queue.poll();
			if (front.left != null) {
				queue.add(front.left);
			}
			if (front.right != null) {
				queue.add(front.right);
			}
		}
		// increment height by 1 for each level
		height++;
	}
	return height;
}