Easy_Question12 : Maximum Depth of Binary Tree

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: 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, 104].
• -100 <= Node.val <= 100

Approach

To find the maximum depth of the tree we can apply a simple recursive approach. Where each function call will represent a subtree which has root node called as ‘root’. We traverse the tree by a recursive function starting from the root node.

So the base case is when the subtree is empty i.e. root is NULL. So we return depth as 0.

if root is not NULL, call the same function recursively for its left child and right child.

As shown in figure, when the two child function return its depth we pick the maximum out of these two subtrees and return this value after adding 1 to it ( Adding current node which is the parent of the two subtrees)

Implementation

import java.io.*;
import java.util.*;

import java.util.*;
import java.lang.*;
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;
      }
}
 

public class TechTwitter
{
// function to find
// the minimum cost
// to reach N-th floor
public static int maxDepth(TreeNode root) {
    if(root==null)
        return 0;
 
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);

    int bigger = Math.max(leftDepth, rightDepth);
 
    return bigger+1;
}
 
// Driver Code
public static void main(String args[])
{
   TreeNode root= new TreeNode(3);
        root.left= new TreeNode(9);
        root.right= new TreeNode(20);
        root.right.left= new TreeNode(15);
        root.right.right= new TreeNode(7);
       
        System.out.println(maxDepth(root));
}
}