Maximum Depth of N-ary Tree Leetcode Solution

In this problem, we are given an N-ary tree, that is, a tree that allows nodes to have more than 2 children. We need to find the depth of a leaf farthest from the root of the tree. This is called maximum depth. Note that the depth of a path is the number of nodes on it.

Example

2

 

/ |

 

3 4 6

 

 

 

9

3

Explanation: The leaf with value 9 is farthest from the root and its depth is 3. So, we print 3.

2

 

/

 

3 6

 

/ |

 

4 7 9

3

Explanation: The leaves with value 4,7 and 9 are farthest from the root and their depth is 3. So, we print 3.

Approach(Recursive)

The maximum depth of a binary tree is calculated by calling the recursive function on left and right children of any node. Similarly, in case of an N-ary tree, we can calculate the maximum depth by calling the recursive function on all the children of any node. This approach is recursive and requires only a single pass of the tree.

 

Algorithm

 

- Create a function maxDepth() to return the maximum depth of a tree whose root is passed to it

- If root is null:

 

- return 0

 

- Initialize a variable maximumDepth to store the maximum depth of N-ary tree

- For every child in the children list of the current root:

 

- set maximumDepth = max(maxDepth(root.left) , maxDepth(root.right))

 

- return maximumDepth + 1

 

Implementation of Maximum Depth of N-ary Tree Leetcode Solution

C++ Program

#includ

 

www.tutorialcup.com/leetcode-solutions/maximum-depth-of-n...

Done