Notebook

104. Maximum Depth level of Binary Tree

Given the root of a binary tree, return ~~its maximum depth~~ the level of the farthest leaf (i.e. the height +1 of the tree).

A binary tree's maximum ~~depth~~ level is the number of nodes along the longest path from the root node down to the farthest leaf node (see here for a reminder on the difference between depth, level and height)

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Example 3:

Input: root = []
Output: 0

Example 4:

Input: root = [0]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
-100 <= Node.val <= 100

Source

In [1]:

# 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

Code

In [2]:

def max_height(root):
    """DFS using bottom up recursion
    we dig until we reach a leaf (height = 0) and we add +1 for
    each node until back to the root.
    We return max(height(root)) = height(tree)
    Note: the question asks for 1+height
    """
    if not root:
        return -1  # proper use of height
    
    left = max_height(root.left)
    right = max_height(root.right)
    return 1 + max(left, right)

In [ ]:

def max_depth(root):
    """Same as above. This is what is actually asked for in this question
    Though strictly speaking depth = counting edges and not nodes
    Note: this solution CAN NOT be applied as such for min depth (see leetcode 111)."""
    if not root:
        return 0   # strictly speaking height(leaf) = 0 ==> height(None) should be -1 (by convention)
    left = max_depth(root.left)
    right = max_depth(root.right)
    return 1 + max(left, right)

In [3]:

def max_depth(root):
    """Same as above.
    Note: this solution CAN be applied as such for min depth (see leetcode 111)."""
    if not root:
        return 0  # strictly speaking height(None) should be -1
    if not root.left and not root.right:        # not strictly
        return 1                                # needed (but speeds up)
    if not root.left:                           # However
        return 1 + max_depth(root.right)        # it would be needed
    if not root.right:                          # if we were looking for
        return 1 + max_depth(root.left)         # min height instead
    return 1 + max(max_depth(root.left), max_depth(root.right))

In [ ]:

def max_depth(root):
    """DFS using Top down recursion
    we dig into the tree, adding +1 at each children
    until we reach a leaf, where we return the depth we calculated so far
    we keep track of the highest value we saw so far
    """
    def dfs(node, depth):
        nonlocal max_depth
        # base case
        if not node:
            if depth > max_depth:
                max_depth = depth
            return
        depth += 1
        left = dfs(node.left, depth)
        right = dfs(node.right, depth)
        return

    max_depth = 0
    dfs(root, 0)
    return max_depth

Follow up:

Solve it both recursively and iteratively.

Code

In [ ]:

def max_depth(root):
    """BFS using a top down iterative approach with a list."""
    if not root:
        return 0
    queue = [(root, 1)]
    depth = 0
    for (node, level) in queue:
        if node:
            depth = level  # last level we see will be the depth
            queue += (node.left, level+1), (node.right, level+1),
    return depth

In [ ]:

from collections import deque

def max_depth(root):
    """BFS using a top down iterative approach with a queue."""
    if not root:
        return 0
    queue = deque()
    queue.append((root, 1))
    depth = 0
    while queue:
        node, level = queue.popleft()
        if node:
            depth = level  # last level we see will be the depth
            queue += (node.left, level+1), (node.right, level+1),
    return depth

In [4]:

def max_level(root):
    """BFS using a bottom up iterative approach with a list."""
    # Start with a level traversal (using a stack)
    queue = [root]
    for node in queue:  
        if node:
            queue += node.left, node.right  # last nodes --> full layer of "None"

    # then, traverse nodes in reverse (i.e from bottom layer)and update their height
    # by conv. height of bottom nodes = 0 (i.e last nodes being "None" have depth = -1)
    height = {None: -1}
    for node in reversed(queue):
        if node:
            height_left = height[node.left]
            height_right = height[node.right]
            height[node] = 1 + max(height_left, height_right)
    return 1+height[root]

In [ ]:

from collections import deque

def max_level(root):
    """BFS using a bottom up iterative approach  with a deque"""
    queue = deque()
    queue.append(root)
    traversal = deque()
    while queue:
        node = queue.popleft()
        if node:
            traversal.appendleft(node)
            queue += node.left, node.right  # last nodes --> full layer of "None"

    height = {None: -1}
    while traversal:
        node = traversal.popleft()
        if node:
            height_left = height[node.left]
            height_right = height[node.right]
            height[node] = 1 + max(height_left, height_right)
    return 1+height[root]

In [ ]:

def max_depth(root):
    """DFS using an iterative approach with a stack."""
    if not root:
        return 0
    stack = [(root, 1)]
    depth = 0
    while stack:
        (node, level) = stack.pop()
        if node:
            depth = max(depth, level)  # keep track of max depth
            stack += (node.left, level+1), (node.right, level+1),
    return depth