Maximum Depth of a Binary Tree

Given a tree data structure , write an algorithm to find the maximum depth of the tree.

Maximum depth is the length of the path from root node to the most distant leaf of the tree.

For example:

Given a tree represented by the array:

[3,9,20,null,null,15,7]

where each three elements in the array represents the root , the left node and the right node.

So the first root node is 3

Its left node is 9

Its right node is 20

And then the left node of the node 9 is null (no left node)

And then the right node of the node 9 is null (no right node)

Then the left node of the node 20 is 15

And the right node of the node 20 is 7.

It can be represented by the below diagram:

Solution:

Use Depth First Search or Breadth First Search.

Approach 1 : Depth First Search

Remember DFS always involves recursion. You keep going deep from each node as you reach the leaf of each tree path.

You do DFS for the left path and then the right path from the root node and then return the maximum depth of the two.

As you reach the end of a DFS search you add 1 to the length.

This keeps getting added until you reach the root and gives us the actual depth of the tree along that path.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    

    public int maxDepth(TreeNode root) {
        
        
        if(root == null){ 

                 return 0;
                         
               }else{
            
            
            int left = maxDepth(root.left);
            
            int right = maxDepth(root.right);
            
            return Math.max(left,right) +1;
        }
        
        
        
        
    }
    
        
}

You can write this in a single line of code as follows:

class Solution{

    public int maxDepth(TreeNode root){

            return root == null? 0 :(Math.max(maxDepth(root.left),maxDepth(root.right))+1);
    }

}

Algorithm:

1. If root is null return 0.
2. If root is not null , do recursive search on the left node and the right node
3. Find the maximum of the two and add 1 to it.
4. Return the value

Time complexity:

We traverse each node once ,so time complexity is O(n) where n is the number of nodes.

Space complexity:

In the worst case where the tree is completely unbalanced (all nodes present along a single path) we will make n recursive calls , so space complexity is O(n)

whereas in the best case where the tree is completely balanced (equal number of left nodes and right nodes) we will make log n recursive calls so space complexity is O(logn)

Approach 2 – Breadth First Search

BFS makes use of queues.

So the basic idea is to :

Add the nodes at each level to a queue

Increment a counter to calculate the depth at that level

Pop all the top elements of the queue at each level and put their children in the queue back.

Do this until the queue is empty.

So at each level you increment the depth , pop all the elements in that level and add all their left and right child nodes (children) to the queue.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    

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

Algorithm:

1.If node is null return 0

2. Create a queue to add the nodes

3. Add the first node

4. Initialize a counter to calculate the depth

5. While the queue is not empty do the following:

6. Increment the counter

7. For all the elements in the queue : pop the element and add their left and child nodes to the queue.

Time complexity:

We traverse each node once so time complexity is O(n)

Space complexity:

We add all the nodes to the queue ,so space complexity is O(n)

That’s it!