Leetcode 104: Maximum Depth of Binary Tree

Post-order depth-first search (DFS)

Link to problem descriptions

Refresher before diving into solutions

Keyword-to-algorithm cue for tree problem

• Maximum width, level order → Breadth-first search (BFS)
• Maximum depth, serializing, validate binary search tree → Depth-first search (DFS)

Also specific to DFS, we could have pre-order, in-order, and post-order keyword-to-algorithm cues as follows:

• Maximum depth: Post-order — left -> right -> node
• Serializing: Pre-order — node -> left -> right
• Binary search tree: In-order — left -> node -> right

Mnemonics for “BFS uses FIFO queue; DFS uses LIFO stack”

• BFS uses queue to store nodes of each level: Bus Fare System uses a queue — First In, First Out (FIFO)
• DFS uses stack for recursion: Dishes after Feast Session forms a stack — Last In, First Out (LIFO)

The “trust the process” principle of recursion

DFS uses recursion. For understanding recursion, involving call stack and keeping in mind that each element of the call stack has a function call with a different argument value (even though they have the same variable name). Implementing recursion can feel uncomfortable until we can follow the “trust the process” principle — breaking a problem down into the simplest possible case (base case) and then building on that solution, step by step, trusting that if you can solve the simpler problem, you can solve the more complex one by repeatedly calling the solver itself (recursive calls).

Analogy

Picture an adventure inside a maze consisting of chambers and cross roads, and we have a team of explorers who need to start at the entrance and figure out the maximum depth of the maze (i.e., the dead end furthest from the entrance).

At each chamber, we can go further to the left or right. Picture ourselves arriving at the entrance, and we want to know how long the left and right paths are, respectively. One way to figure out the answer is to send two explorers out, one explores the left path, and another explores the right path, and we wait at the entrance until these two explorers return with their respective answers, and then we can make a decision about the max_depth based the maximum value we obtain between the two explorers.

This left -> right -> node is a post-order DFS pattern. And this pattern could repeat in recursive pattern. That is, each of the explorer we send out could also arrive at the next cross roads, ask two other explorers to go down left and right and report back. Each of these repeat work at a different chamber, and each time the decision at the node can only be made when the left and right explorers have returned with an answer.

This forms the following recursive pattern:

left_depth = maxDepth(node.left)
right_depth = maxDepth(node.right)

return max(left_depth, right_depth) + 1 # Here `+1` accounts for root node

The two recursive calls continue during recursion descent until the base case root is None is hit. The return max(left_depth, right_depth) + 1 are pending returns within each call stack element that only gets executed during recursion ascent.

Implementation

Putting these together, the post-order DFS implementation is as follows:

from typing import Optional


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


class Solution:
    def maxDepth(self, root: Optional[TreeNode]):
        # Base case: When receiving an empty tree
        #   or previous node no longer has a subtree,
        #   we either have an empty tree
        #   or have reached the maximum depth of a subtree
        #   At this point, we stop going deeper and return maximum depth as 0
        if root is None:
            return 0

        # Recursive calls
        #   1. How deep did the left side go?
        max_depth_left = self.maxDepth(root.left)
        #   2. How deep did the right side go?
        max_depth_right = self.maxDepth(root.right)

        # conceptually akin to a key decision point in backtracking.
        #   We "choose" the path (or branch) that offers a greater depth
        # A classical use case of post-order DFS traversal: left-right-node:
        #   process both subtrees before making a decision about
        #   the current node
        return max(max_depth_left, max_depth_right) + 1

Time and space complexity

With n denotes the total number of nodes in the tree

• Space complexity: Space complexity is dominated by the size of the call stack used by recursion. In best case scenario when we work with a perfectly balanced binary tree, the call stack size is the same as the total height of the tree. This gives us best-case space complexity of O(log n). In worst case scenario when we have a completely imbalanced tree (it becomes a singly linked list), the height of the tree equals the total number of nodes and we get worse-case space complexity of O(n)
• Time complexity: O(n) — Since we traverse each node exactly once

Example unit tests (pytest)

import pytest


@pytest.fixture
def simple_tree():
    """Create a simple binary tree with depth of 3 as test data
            1
          /   \
        2       3
      /   \   /   \
    4      5 6     7
    """
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    node6 = TreeNode(6)
    node7 = TreeNode(7)
    node2 = TreeNode(2, left=node4, right=node5)
    node3 = TreeNode(3, left=node6, right=node7)
    root = TreeNode(1, left=node2, right=node3)

    return root


def test_max_depth_of_simple_tree(simple_tree):
    assert Solution().maxDepth(simple_tree) == 3


def test_max_depth_of_empty_tree():
    assert Solution().maxDepth(None) == 0


def test_max_depth_of_single_node_tree():
    assert Solution().maxDepth(TreeNode(1)) == 1

Supplement information

Height h vs. number of nodes n for a perfectly balanced binary tree

A “completely balanced” tree, often called a “perfect binary tree,” is a special type of binary tree where every level of the tree is fully filled. In other words, every internal node has exactly two children, and all the leaf nodes are at the same level.

Now, let’s look at the relationship between the number of nodes n and the height h of a perfect binary tree.

Height 0 (root only):

• Number of nodes = 20=120=1

Height 1:

• Number of nodes in level 0 (root) = 2⁰ = 1
• Number of nodes in level 1 = 2¹
• Total nodes = 1 + 2 = 3

Height 2:

• Number of nodes in level 0 (root) = 2⁰ = 1
• Number of nodes in level 1 = 2¹ = 2
• Number of nodes in level 2 = 2² = 4
• Total nodes = 1 + 2 + 4 = 7

From the above examples, we can see a pattern:

• For a perfect binary tree of height h, the total number of nodes n will be: n = 2⁰ + 2¹ + 2² + … + 2^h. This is a geometric series and sums to n=2^(h+1) — 1

If we rearrange to solve for ℎh in terms of n: h ~ log⁡2(n+1) — 1

The key insight is that the height h grows logarithmically with the number of nodes n in a perfect binary tree.