Maximum Depth Of Binary Tree - Leetcode Solution

Problem Statement:

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution:

This problem can be solved easily using a recursive approach. We can use Depth First Search (DFS) to calculate the maximum depth of the binary tree. We will calculate the depth of the left subtree and the depth of the right subtree recursively. Then we will take the maximum of these two values and add one to it, as the root node is at depth 1. The resulting value will be the maximum depth of the binary tree.

Here is the algorithm for calculating the maximum depth of a binary tree using DFS:

1. If the given binary tree is empty, return 0.
2. Calculate the depth of the left subtree recursively by calling the maximumDepth function on the left child of the root node.
3. Calculate the depth of the right subtree recursively by calling the maximumDepth function on the right child of the root node.
4. Take the maximum of the two depths and add one to it to get the maximum depth of the binary tree.
5. Return the maximum depth.

Here is the Python code for the above algorithm:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maximumDepth(root: TreeNode) -> int:
    if root is None:
        return 0
    left_depth = maximumDepth(root.left)
    right_depth = maximumDepth(root.right)
    return max(left_depth, right_depth) + 1

We have defined the TreeNode class to represent each node of the binary tree. The maximumDepth function takes the root node of the binary tree as input and returns the maximum depth of the binary tree.

We start by checking if the root node is empty. If it is, we return 0 as the depth.

Next, we calculate the depth of the left subtree recursively by calling the maximumDepth function on the left child of the root node. Similarly, we calculate the depth of the right subtree recursively by calling the maximumDepth function on the right child of the root node.

Once we have calculated the depths of the left and right subtrees, we take the maximum of the two values and add one to it to get the maximum depth of the binary tree.

Finally, we return the maximum depth.

This solution has a time complexity of O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(h), where h is the height of the binary tree, as the maximum depth of the recursive call stack is equal to the height of the tree.

1