Teaching Kids Programming – Maximum Depth of N-ary Tree via Depth First Search or Breadth First Search Algorithms


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a n-ary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 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

n-ary-tree-max-depth Teaching Kids Programming - Maximum Depth of N-ary Tree via Depth First Search or Breadth First Search Algorithms algorithms BFS DFS python teaching kids programming youtube video

Maximum Depth of Two N-nary Trees

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 total number of nodes is in the range [0, 104].
The depth of the n-ary tree is less than or equal to 1000.

Previously, we know we can compute the Maximum Depth for a Binary Tree via Recursive Depth First Search Algorithm or Breadth First Search Algorithm. Computing the Maximum Depth for a N-ary Tree is no much different.

A N-ary Tree can be defined as:

1
2
3
4
5
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=[]):
        self.val = val
        self.children = children
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=[]):
        self.val = val
        self.children = children

Depth First Search Algorithm to Compute the Maximum Depth of N-ary Tree

With Recursion, we can implement the Depth First Search Algorithm intuitively. The depth for the current Root is the maximum of the Depth for its children nodes plus one.

1
2
3
4
5
6
7
8
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        ans = 0
        for i in root.children:
            ans = max(ans, self.maxDepth(i))
        return ans + 1
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        ans = 0
        for i in root.children:
            ans = max(ans, self.maxDepth(i))
        return ans + 1

We can use the max function that will get the maximum value for a list/array – and we can also specify the default value in case the argument to the max function is None.

1
2
3
4
5
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        return max([self.maxDepth(i) for i in root.children], default=0) + 1
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        return max([self.maxDepth(i) for i in root.children], default=0) + 1

Time and Space complexity is O(N) where N is the number of the nodes for the given N-ary tree.

Breadth First Search Algorithm to Compute the Maximum Depth of N-ary Tree

For Breadth First Search Algorithm, we use a queue – we can pop all Nodes from the queue (as they belong to the same level) and then we enque with all the children nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        q = deque([(root)])
        ans = 0
        while q:
            ans += 1
            n = len(q)
            for _ in range(n):
                cur = q.popleft()
                for c in cur.children:
                    q.append(c)
        return ans
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        q = deque([(root)])
        ans = 0
        while q:
            ans += 1
            n = len(q)
            for _ in range(n):
                cur = q.popleft()
                for c in cur.children:
                    q.append(c)
        return ans

We then just need a variable to store the current depths and when the BFS stops with no nodes in the queue, we have the maximum depth for the current N-ary tree.

Alternatively, we can store an additional information of the node level, and then we pop out one node at a time – and we append the children nodes, we shall also append the level which is current’s level plus one.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        q = deque([(root, 1)])
        ans = 0
        while q:
            cur, lvl = q.popleft()
            ans = max(ans, lvl)
            for c in cur.children:
                q.append((c, lvl + 1))                
        return ans
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        q = deque([(root, 1)])
        ans = 0
        while q:
            cur, lvl = q.popleft()
            ans = max(ans, lvl)
            for c in cur.children:
                q.append((c, lvl + 1))                
        return ans

The Time/Space complexity of BFS is the same as the DFS – which is O(N). The DFS uses a stack (implicitly by Recursion), and a BFS uses a queue.

Compute the Maximum Depth for a N-ary Tree:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
949 words
Last Post: Teaching Kids Programming - Multi-source Breadth First Search Algorithm (Minimum Number of Moves to Capture the King)
Next Post: How RNG Software Determines Online Progressive Jackpot Winners?

The Permanent URL is: Teaching Kids Programming – Maximum Depth of N-ary Tree via Depth First Search or Breadth First Search Algorithms

Leave a Reply