Notebook

559. Maximum Depth level of N-ary Tree

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

The 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)

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 5

Constraints:

The ~~depth~~ level of the n-ary tree is less than or equal to 1000.
The total number of nodes is between [0, 10⁴].
See here for a reminder on the difference between depth and level.

Source

In [1]:

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children  # children = list

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

    if not root.children:  # needed to avoid max(node for node in [])  --> throws an error
        return 0    # proper use of height(leaf) = 0)

    return max(max_height(node) for node in root.children) + 1

In [3]:

def max_depth(root):
    """Same as above. This is actually what is asked for in the question
    Though strictly speaking depth = counting edges and not nodes
    """
    if not root:
        return 0  # strictly speaking height(leaf) = 0 ==> height(None) should be -1 (by convention)
   
    if not root.children:  # base case is needed to avoid max(None)  --> throws an error
        return 1

    # recursive relation
    return max(max_depth(node) for node in root.children) + 1

In [4]:

def max_depth(root):
    """alternative version of above solution"""
    def dfs(node):
        # base cases
        if not node:
            return 0
        if not node.children:
            return 1

        max_depth = 0
        for child in node.children:
            child_depth = 1 + dfs(child)
            max_depth = max(max_depth, child_depth)
        return max_depth

    return dfs(root)

In [5]:

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
    """
    def dfs(node, depth):
        # base case
        if not node:
            return 0
        depth += 1
        max_depth = depth
        for child in node.children:
            max_depth = max(max_depth, dfs(child, depth))
        return max_depth

    depth = dfs(root, 0)
    return depth

In [6]:

def max_depth(root):
    """alternative version of above solution"""
    def dfs(node, depth):
        nonlocal max_depth
        # base case
        if not node:
            return
        depth += 1
        if not node.children:
            if depth > max_depth:
                max_depth = depth
            return
        for child in node.children:
            dfs(child, depth)
        return

    max_depth = 0
    dfs(root, 0)
    return max_depth

Follow up:

Solve it both recursively and iteratively.

Code

In [7]:

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:
        depth = level  # last level we see will be the depth
        queue += [(child, level+1) for child in node.children]
    return depth

In [ ]:

from collections import deque

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

In [ ]:

def max_level(root):
    """BFS using a bottom up iterative approach with a list."""
    if not root:
        return 0

    queue = [root]
    for node in queue:  
        if node:
            queue += [child for child in node.children] # last nodes --> full layer of "None"

    height = {}  # no need for None:0 (as opposed to BST - see leetcode #104) None is never added to stack
    for node in reversed(queue):
        if not node:
            continue
        if node.children == []:
            height[node] = 1
        else:
            height[node] = 1 + max(height[n] for n in node.children)
    return height[root]

In [ ]:

def max_level(root):
    """BFS using a bottom up iterative approach with a deque."""
    if not root:
        return 0

    queue = deque()
    queue.append(root)
    traversal = deque()
    while queue:
        node = queue.popleft()
        if node:
            traversal.appendleft(node)
            queue += [child for child in node.children] # last nodes --> full layer of "None"

    height = {}  # no need for None:0 (as opposed to BST - see leetcode #104) None is never added to stack
    while traversal:
        node = traversal.popleft()
        if not node:
            continue
        if node.children == []:
            height[node] = 1
        else:
            height[node] = 1 + max(height[n] for n in node.children)
    return height[root]

In [8]:

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()
        depth = max(depth, level)  # keep track of max depth
        stack += [(child, level+1) for child in node.children]
    return depth