Maximum Depth of Binary Tree — LeetCode 104 (Easy)

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.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Explanation

By understanding the above problem all we need to do is to find the height of our tree we can find it by using multiple methods recursion, bfs (breadth first search) and dfs (depth first search)

So we will see recursion method first

Method 1

Let’s draft the base cases i.e., if the root is null the we have to return 0

if we consider a tree all options we have are left and right we can either go left or right so we need to call our recursion fuction with max of left and right side so we will get the maximum depth of the sides it can either be the left or right

Code for recursion

If we check the code is simple and very little code all the magic happens in the single line of the code

return 1 + max(self.maxDepth(root.right), self.maxDepth(root.right))

Method 2 (BFS)

As the BFS name suggests first we will search the Breadth of the tree and then goes to the next level of the tree so at each level we increment a counter and at the final we will return the counter that will be the height of the tree.

Let’s see how we can acheive this

• First all we need is a queue (as definatino suggests queue is first in first out what ever we insert first will be poped first)
• first we add the root to the queue
• then we a do a loop untill the queue is empty and then we pop each item in the queue
• then the options we have are left and right so if the left and right not None we add them to queue accordingly.
• So our loop will continue untill we reach the end of the tree i.e., we gone trought all the items in the tree
• And we increment the counter after each loop
• Finally we return the counter which is our depth of the tree

Let’s see the code

Here we reached the end of the code

Hope you liked my explanation and code, Thanks for reading :)