559. Maximum Depth of N-ary Tree (Python)

Related Topic

Breadth-First-Search.

Description

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

Sample I/O

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

Note

• The depth of the n-ary tree is less than or equal to 1000.
• The total number of nodes is between [0, 10^4].

Methodology

Create a queue and append the root and initial depth to queue. Use BFS traversal tree level by level from root. For each root, append the root’s children nodes and depth+1 to queue. The last node of the tree will also give us the final depth of the tree

We can also use DFS to get the answer but the performance is far worse than BFS.

Code (BFS)

def maxDepth(self, root: 'Node') -> int:
        if not root: return 0
        queue = collections.deque()
        depth = 1
        queue.append((root,depth))
        while queue:
            node, depth = queue.popleft()
            if node.children:
                for child in node.children:
                    queue.append((child,depth+1))
        return depth

BigO

We traversal all elements of tree once so total time complexity is O(n) where is the size of the tree