104. Maximum Depth of Binary Tree#

Difficulty: Easy

Link to Problem: To see the Invert Binary Tree problem on LeetCode, click here!

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.

Constraints:

  • The number of nodes in the tree is in the range \([0, 10^4]\).

  • -100 <= Node.val <= 100

# 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

def maxDepth(root):
    # Base case: If the root is None, the depth is 0.
    if root is None:
        return 0
    
    # Recursively calculate the maximum depth of the left and right subtrees.
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    # Return the maximum depth of the tree by adding 1 to the maximum depth of the subtrees.
    return max(left_depth, right_depth) + 1

Explanation:#

Let’s go through the code step by step to understand how it works:

  1. We start by defining a TreeNode class to represent the nodes of the binary tree. Each node has three attributes:

    • val: the value stored in the node.

    • left: a reference to the left child node.

    • right: a reference to the right child node.

  2. The maxDepth function is the main function that calculates the maximum depth of the binary tree. It takes a single argument, root, which is the root node of the binary tree.

  3. In the maxDepth function, we have a base case:

    • If the root is None, it means we have reached the end of a branch of the tree (a leaf node or an empty subtree). In this case, the depth is 0 because there are no nodes to count.

  4. If the root is not None, we recursively calculate the maximum depth of the left and right subtrees:

    • We call maxDepth on the root.left to calculate the maximum depth of the left subtree and store it in the variable left_depth.

    • We call maxDepth on the root.right to calculate the maximum depth of the right subtree and store it in the variable right_depth.

  5. Finally, we return the maximum depth of the tree by taking the maximum of left_depth and right_depth and adding 1 to it. This is because we are counting the current level as well.

Test cases#

### Example 1
# Input: root = [3,9,20,null,null,15,7]

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(maxDepth(root))

3

In this example, we create a binary tree based on the given input [3,9,20,null,null,15,7] and calculate its maximum depth, which is 3. The tree structure is as follows:

    3
   / \
  9  20
    /  \
   15   7

So, the maximum depth is the length of the longest path from the root to a leaf node, which is 3 in this case.

### Example 2
# Input: root = [1,null,2]

root = TreeNode(1)
root.right = TreeNode(2)

# Calculate the maximum depth of the tree and print the result
print(maxDepth(root))

2

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

  • The time complexity of the maxDepth function is \(O(N)\), where \(N\) is the number of nodes in the binary tree.

  • This is because in the worst case, the function visits every node exactly once in a depth-first manner.

  • The recursion explores all nodes of the tree, so the time complexity is linear with respect to the number of nodes.

Space Complexity:

  • The space complexity of the maxDepth function is \(O(H)\), where H is the height of the binary tree.

  • In the worst case, if the binary tree is completely unbalanced (skewed), the recursion stack can go as deep as the height of the tree.

  • In the best case, if the binary tree is perfectly balanced, the height is \(O(log\ N)\), where \(N\) is the number of nodes.

  • Therefore, the space complexity can vary from \(O(log\ N)\) to \(O(N)\) depending on the shape of the tree.

  • In addition to the recursion stack, there is a small constant amount of space used for variables and function call overhead.

In summary:

  • The time complexity of the code is \(O(N)\) as it visits each node once.

  • The space complexity is \(O(H)\), where H is the height of the tree, which can vary from \(O(log\ N)\) to \(O(N)\) depending on the tree’s shape.