Maximum Depth Of A Binary Tree

Easy
0/40
Average time to solve is 15m
profile
Contributed by
15 upvotes
Asked in companies
FacebookTata Consultancy Services (TCS)Walmart

Problem statement

You are given the root node of a binary tree with N nodes, whose nodes have integer values. Your task is to find the maximum depth of the given Binary tree.

Depth of a binary tree is the same as its height. In simpler terms, you have to find the total number of nodes encountered while moving from the root node to the farthest leaf node, along the longest path of the binary tree.

Example:-

example

If we are given the above binary tree as input then moving from root node(5) to the farthest leaf node(50), the path formed will be [ 5->10->25->35->40->45->50 ]. The total number of nodes encountered is 7, therefore the maximum depth of the binary tree is 7.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains a single integer T, representing the number of test cases.

The first and only line of each test case contains the values of the nodes of the tree in the level order form ( -1 for NULL node) Refer to the example for further clarification.
Example:
Consider the following binary tree

example

The input of the tree shown in the above image will look like: 

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are null (-1).
Output Format:
For each test case, print a single integer “N” representing the maximum depth of the input binary tree. 
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 3000
0 <= data <= 10^9

Time Limit: 1sec
Sample Input 1:
3
1 2 3 -1 -1 -1 -1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
1 2 -1 3 -1 4 -1 5 -1 -1 -1
Sample Output 1:
2
4
5
Explanation For Sample Input 1:
In the first test case,  the given tree has the longest path along [ 1 -> 2 ] or [ 1->3 ], hence the maximum depth is 2.

In the second test case, the given tree has the longest path along [ 1 -> 2 -> 4-> 7 ], hence the maximum depth is 4.

In the thirds test case, the given tree is a left-skewed tree having the longest path along [ 1 -> 2 -> 3-> 4 ->5 ], hence the maximum depth is 5.
Sample Input 2:
4
1 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1
1 2 -1 3 -1 4 -1 5 -1 6 -1 7 -1 -1 -1
1 2 3 -1 -1 4 -1 -1 -1 
1 -1 -1 
Sample Output 2:
3
7
3
1    
Hint

Can we recursively find the max depth of the left and the right child?

Approaches (2)
Recursive approach

The idea is to use DFS (Depth First Search) traversal and recursively find the maximum depths of the left subtree and right subtree, returning the max of both the values plus 1 (counting the root node) as our answer.

 

  • We are given a function ‘findMaxDepth’ which takes the root node of the binary tree “ROOT”  as the parameter and returns an integer which is the maximum depth of the binary tree.
  • First, we will take care of our base condition and check whether our ROOT node is NULL or not. If it is NULL, we will return 0, Implying that there is no node in the given tree and the height returned will be 0.
  • Now, we will compute the maximum depth of both our left and the right subtree by recursively calling our function ‘findMaxDepth’ on the left child and the right child of the ‘ROOT’ node.
  • Finally, we will find the maximum of both the maxDepths of left and right subtree. We will return the maximum depth plus 1 (counting the root node) as our final answer.
Time Complexity

O(N), where N is the number of nodes in the given binary tree.

 

As clearly seen, we are doing DFS traversal and our program visits every node exactly once. Hence the time complexity is of the order O(N).

Space Complexity

O(N), where N is the number of nodes in the given binary tree.

 

As this is a recursive algorithm and due to stack space, our overall space complexity will be of the order O(N).

Code Solution
(100% EXP penalty)
Maximum Depth Of A Binary Tree
Full screen
Console