104. Maximum Depth of Binary Tree — LeetCode(Python)

I got you!

Problem:

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

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

Solution:

1. Recursive —

Explanation —

We can easily solve this problem using bottom-up recursion.

If we know the height of the left and right subtrees, we can calculate the height of our current node by simply adding 1 to the greater height.

So, we recursively call the function on both left and right subtrees and return the updated answer.

Time and Space Complexity —

Since we are visiting all nodes in the tree a constant number of times, we can say that our algorithm requires a linear amount of time to run.

Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.

Thus, if n is the number of nodes in the given binary tree,

Time Complexity: O(n)

Space Complexity: O(n)

2. Iterative —

Explanation —

We can use a breadth-first search instead of a depth-first search to solve this problem iteratively.

We write a standard BFS traversal algorithm and keep storing the nodes in our tree level-wise in a queue.

Then, we keep popping / enqueueing from the queue until a level is fully traversed and while doing so, we add nodes in the next level to our queue.

After every level traversed, we increment the value of levels.

Finally, we return levels.

Time and Space Complexity —

Since we are visiting each node in the tree only a constant number of times, we can say that our algorithm requires linear amount of time to run.

Also, our queue will be storing a maximum of (n / 2) nodes when it reaches the final level. So, we assume the space complexity to be linear in the worst case.

Thus, if n is the number of nodes in the tree.

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏