It’s a common and basic type of problem. The problem title is self-explanatory. We all know about a binary tree. To solve this problem, we have to find the maximum depth of a binary tree.
We can solve this using both DFS and BFS algorithms. I am going to use the DFS solution.
We can implement the DFS algorithm both recursively and iteratively. The recursive solution is easier and cleaner. So let’s see the recursive one.
Coding Part
If there is no node or the tree is empty, the depth is 0. So this will be the base case in our recursive solution.
Now let’s think, if there is only one node in a binary tree, what will be the depth? The depth will be 1. As we start from the root, the depth of the root node will be 1. To know which subtree has the maximum depth, we can declare the recursive case: 1 + max(left_subtree, right_subtree).
If there is no node or subtree of the root, we will get 0 as we set our base case. So If there is only one node, the answer will be 1 (1 + max(0, 0)). Otherwise, it will continue to check and return the maximum.
Let’s see the code for better understanding.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
I hope you got the idea. You can also try other solutions.
Happy Learning.
Happy Coding.