JavaScript Solution to Maximum Depth of N-ary Tree
Prerequisite: Tree Traversal In JavaScript
For our last ‘She’s coding’ data structure and algorithm practice event, we chose to solve maximum depth of N-ary tree problem(link). We had interesting discussion about approaches to solve it. In the following blog, I’ll share the common solution to this problem.
Problem:
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: 3Example 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: 5Constraints:
- The depth of the n-ary tree is less than or equal to 1000.
- The total number of nodes is between [0, 10^4].Solution:
N-ary Tree is a common data structure to encounter, unlike binary tree, which has left and right children, n-ary tree’s node in this problem has value and children attributes.
The input is the root tree, and output is the integer that represents the depth of the given tree. First thing to consider is if the given root is null or not. After validating the root, to count the level, we traverse the tree. Because we need to count the level, we also need a variable to store the levels, so when the traversing is done, we can return the depth of the tree. The key of the solution is traversing. When it comes to traversing a tree, the common approaches are depth-first-search and breath-first-search. Let’s see how we solve it both ways.
Depth-first-search
Breadth-first-search
I hope this could offer you some insights about solving the similar questions in the future.
