Technical Interview Question: Maximum Depth of Binary Tree

A binary tree is a data structure consisting of nodes, where each node has at most two child nodes, referred to as the left child and the right child. The depth of a binary tree is the maximum distance from the root node to any leaf node. Write a function to find the maximum depth of a binary tree.

Input:

    3
   / \
  9  20
    /  \
   15   7

Output: The maximum depth is 3.

Given the binary tree above, the maximum depth is 3 since the longest path from the root node to a leaf node is 3 -> 9 -> 20 -> 15.

Answer and Explanation:

To find the maximum depth of a binary tree, we can use a recursive approach. The basic idea is to traverse each left and right subtree and keep track of the maximum depth.

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

def maxDepth(root):
    if root is None:
        return 0
    else:
        left_depth = maxDepth(root.left)
        right_depth = maxDepth(root.right)
        return max(left_depth, right_depth) + 1

In this recursive approach, the function maxDepth takes the root of the binary tree as input and returns the maximum depth of the tree.

1. If the root is None, the function returns 0 as the depth.
2. Otherwise, the function recursively calculates the maximum depth of the left and right subtrees.
3. The maximum depth of the current node is the maximum of the depths of its left and right subtrees, plus 1 for the current level.

Using the above function with the given binary tree, we can find the maximum depth as follows:

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(maxDepth(root))  # Output: 3

The maximum depth of the binary tree is computed as 3, which is the expected output. This approach gives us the maximum depth of the binary tree in an efficient and straightforward manner.