# Maximum Depth of N-ary Tree — Day 65(Python)

Today, I thought of solving an N-ary Tree question. Since I have never solved an N-ary Tree question, I thought of starting with something which was tagged easy on leetcode. Let us look into the question without wasting much time.

**559****. Maximum Depth of N-ary Tree**

Given an 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

**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 of the n-ary tree is less than or equal to
`1000`

. - The total number of nodes is between
`[0, 104]`

.

If this question was asked for a Binary Tree, Breadth-First Search or Depth-First Search would be the algorithm to be used. Can we try using the same logic for an N-ary Tree? What modification do we have to make in order to make the algorithm work?

We will be using the Breadth-First search approach to solve this problem.

We would need a queue that will store the nodes whose children we need to visit next. We will be using another queue that will keep track of all the children of nodes at a particular level. Each time we hit a new level the variable that keeps track of depth will be incremented.

Wait, how do we keep track of children though? We can have a loop that will visit all the children of the required node. Let us look into the code snippet.

class Node:

def __init__(self, val=None, children=None):

self.val = val

self.children = childrenclass MaxDepthFinder:

def maxDepth(self, root: 'Node') -> int:

if root == None:

return 0

else:

depth = 0

nodes_queue = [root]

next_nodes_queue = []

while(nodes_queue):

node_out = nodes_queue.pop(0)

for child in node_out.children:

next_nodes_queue.append(child)

if nodes_queue == []:

nodes_queue, next_nodes_queue = next_nodes_queue, nodes_queue

depth += 1

return depth

**Complexity analysis.**

**Time Complexity**

We are visiting each node once, hence the time complexity is O(N) where N is the number of nodes.

**Space Complexity.**

We are visiting each node once and storing it in the queue. In the worst case, if all the children are in the same x level, we might have to hold all the nodes in the queue, hence the space complexity is O(N) where N is the number of nodes.