Maximum Depth of Binary Tree (Leet Code-104)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 104. This is a Leet code problem named Maximum Depth of Binary Tree. We will solve it using python and it is the best space and time-optimized solution.

Question of 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.

Example

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, 10⁴].
-100 <= Node.val <= 100

Approach to solve Maximum Depth of Binary Tree

To solve this problem we will recursively find the height of the left child and the right child. After that, we return the maximum of left height or right height which is maximum.

Algorithm

This method performs the following steps for a given input binary search tree:

Create an inner function to find the height.
Check base condition i.e. if the node is node then return 0.
Find the height of the left child by recursively calling the height function.
Find the height of the right child by recursively calling the height function.
return the maximum of the left height or right height.
End inner function

Python Code for Maximum Depth of Binary Tree

# 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:
        #inner function to calculate height
        def height(node):
            #base case
            if node is None:
                return 0
            else:    
                # compute the height of left subtree
                lHeight = height(node.left)
                # compute the height of left subtree
                rHeight = height(node.right)

                # return the height of larger sub tree                 
                return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)
            
        return height(root)