The blog for Design Patterns, Linux, HA and Myself!

25
August 2020

In this article we’ll be solving the problem: Maximum Depth of N-ary Tree. This problem belongs to Tree Traversal category and just like the problem, Increasing Order Search Tree, and Merge Two Binary Trees this problem also requires a slight modification in a simple Tree Traversal approach.

` ````
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).
Constraints:
The depth of the n-ary tree is less than or equal to 1000.
The total number of nodes is between [0, 10^4].
```

As mentioned earlier, this problem requires a small change in the tree traversal function. To solve this problem, I’ll
be using the `preOrder`

tree traversal. Here’s the tree that’ll be our example:

While traversing the tree using the pre order approach, we’ll also pass an integer to each of the node. This integer will be the current depth. Once we reach to a node, we’ll increment the depth by 1 and then pass the depth to all of its children.

There will also be one more variable, `maxDepthValue`

, that’ll contain the maximum value for the depth that a node has
ever received and while traversing the nodes we’ll update the `maxDepthValue's`

.

Here the code for that:

```
type Node struct {
Val int
Children []*Node
}
// maxDepthValue contains the maximum depth a node has ever received.
// While traversal, the current height is compared with this variable.
// If the current height is greater than maxDepth then maxDepthValue is updated
// with the current height
var maxDepthValue int
func maxDepth(root *Node) int {
maxDepthValue = 0
if root == nil {
return 0
}
preOrder(root, 0)
return maxDepthValue
}
func preOrder(root *Node, currentDepth int) int {
currentDepth++
if currentDepth > maxDepthValue {
maxDepthValue = currentDepth
}
if root.Children != nil {
for _, child := range root.Children {
preOrder(child, currentDepth)
}
}
return 0
}
```

This code is available here @ GitHub as well.

Here, `preOrder`

is called by `maxDepth`

function and then `preOrder`

calls itself recursively for each of the children.

This image presents the values for `currentDepth`

after every execution of `preOrder`

Loading Comments...

- All Elements in Two Binary Search Trees Solution
- Construct Binary Search Tree From Preorder Traversal Solution
- Maximum Binary Tree Solution
- Sum of Nodes With Even Valued Grandparent Solution
- Deepest Leaves Sum Solution
- Symmetric Tree or Mirror Tree Solution
- Diameter of Binary Tree Solution
- Binary Tree Paths Solution
- Cousins in Binary Tree Solution
- Sum of Left Leaves Solution
- Same Tree or Equal Tree Solution
- Minimum Absolute Difference in BST Solution
- Construct String From Binary Tree Solution - Leetcode
- Two Sum IV - Input is a BST Solution - Leetcode
- Convert BST to Greater Tree Solution - Leetcode
- Convert Sorted Array to Binary Search Tree Solution
- Average of Levels in Binary Tree Solution
- Leaf Similar Trees Solution - Leetcode
- Sum of Root to Leaf Binary Numbers - Leetcode
- Univalued Binary Tree - Leetcode
- Maximum Depth of N Ary Tree - Leetcode
- Increasing Order Search Tree - Leetcode
- Merge Two Binary Trees Solution
- Range Sum of BST - Leetcode