Maximum Depth of Binary Tree

Finding the maximum depth of a binary tree is a straightforward problem that can be solved recursively. The depth of a tree is the length of the longest path from the root to a leaf. Here’s how you can approach it:

  1. Base Case: If the current node is None, return 0 as the depth. It means you have reached a leaf node.
  2. Recursive Call: Call the function recursively for both left and right children.
  3. Calculate Depth: The depth of the current node will be the maximum of the depths of its left and right children plus 1 (to count the current node itself).

Here’s the code:

1
2
3
4
5
6
7
8
9

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        return max(left_depth, right_depth) + 1

This code calculates the depth by exploring all paths from the root to the leaves. The recursive call to the left and right children helps to traverse the entire tree, and the max function ensures that only the longest path is considered.

The time complexity of this code is (O(n)), where (n) is the number of nodes in the tree, and the space complexity is (O(h)), where (h) is the height of the tree (which is also the maximum depth). This accounts for the space required by the recursive call stack.

Recursion

  1. What is the base case?
    • Empty tree => 0
  2. Whare the recursive cases?
    • declare left and right
    • Add 1 to the result of max of those subproblems
  3. Return the result
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
    if root.nil?
        return 0
    end

    left = max_depth(root.left)
    right = max_depth(root.right)

    return 1 + [left, right].max    
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
    if root.nil?
        return 0
    end

    left = max_depth(root.left)
    right = max_depth(root.right)

    1 + [left, right].max
end

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
    result = 0

    if root.nil?
        return 0
    end

    left = 1 + max_depth(root.left)
    right = 1 + max_depth(root.right)

    [left, right].max
end

Identifying Problem Isomorphism

“104. Maximum Depth of Binary Tree” is about calculating the maximum depth (or height) of a binary tree from its root to the farthest leaf node.

An isomorphic problem to this is “111. Minimum Depth of Binary Tree”. In the minimum depth problem, the goal is to find the minimum depth of a binary tree, which is the shortest distance from the root to the nearest leaf node.

Both problems require traversing the tree and calculating the depth of it. While the maximum depth problem asks for the longest root-to-leaf path, the minimum depth problem asks for the shortest such path. Therefore, both problems are essentially about measuring the depth of a binary tree, making them isomorphic.

1
2
3
4
5
6
7

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(root, depth):
            if not root: return depth
            return max(dfs(root.left, depth + 1), dfs(root.right, depth + 1))

        return dfs(root, 0)

Problem Classification

The problem can be classified as follows:

  1. Binary Trees: The problem involves working with binary trees. Understanding the structure and properties of binary trees, such as the concept of depth, is central to solving this problem.

  2. Tree Traversal: The problem requires traversing a binary tree in a depth-first manner. This means visiting a tree node and then recursively visiting its children, starting with the left child and then the right.

  3. Depth Calculation: The core task in this problem is to calculate the maximum depth of a binary tree. This requires an understanding of what depth means in the context of a tree - the distance from the root to the farthest leaf node.

  4. Recursion: The problem is naturally addressed using a recursive approach. Understanding how recursion can be used to traverse a tree and perform calculations at each node is crucial.

This classification helps in understanding the types of techniques and concepts that are required to approach and solve the problem. It allows one to identify the problem as one that involves binary tree traversal and manipulation using recursive techniques.

Language Agnostic Coding Drills

  1. Understanding Binary Trees: The problem involves finding the maximum depth of a binary tree. This requires knowledge about binary trees and their properties.

  2. Depth-First Search (DFS): The solution to this problem involves performing a DFS on a binary tree. This is a common technique used in tree and graph problems.

  3. Recursive Functions: This problem involves writing a recursive function to solve the problem. Understanding the base case and the recursive case is key to this problem.

  4. Working with Optional Types: In this problem, the input can be an Optional[TreeNode], meaning it can either be a TreeNode or None. Understanding this can prevent potential errors.

Targeted Drills in Python

  1. Understanding Binary Trees:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

# Create a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
  1. Depth-First Search (DFS):

For this concept, you should understand how DFS works and how it can be implemented. Writing code for this without using recursion is not straightforward, so let’s move on to recursion.

  1. Recursive Functions:
1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # prints 120
  1. Working with Optional Types:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from typing import Optional

def greeting(name: Optional[str] = None):
    if name is None:
        print("Hello, stranger!")
    else:
        print(f"Hello, {name}!")

greeting("Alice")  # prints "Hello, Alice!"
greeting()  # prints "Hello, stranger!"

Problem-Specific Drill:

Now let’s combine all of these concepts into a drill specific to the problem at hand:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from typing import Optional

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

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(root, depth):
            if not root: return depth
            return max(dfs(root.left, depth + 1), dfs(root.right, depth + 1))
                       
        return dfs(root, 0)

# Create a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

# Find the maximum depth
solution = Solution()
print(solution.maxDepth(root))  # prints 3

This drill exercises all the necessary concepts and builds up to the final solution. Each concept is demonstrated in isolation and then integrated into the final solution.