FastPrepMaximum Depth of an N-ary Tree
Problem · Tree

Maximum Depth of an N-ary Tree

Learn this problem
● EasyAmazon logoAmazonNEW GRADONSITE INTERVIEW
See Amazon hiring insights

Problem statement

A rooted N-ary tree has nodes numbered from 0 through parent.length - 1. The single root has parent -1; every other entry parent[i] is the index of node i's parent.

Return the maximum depth of the tree, measured as the number of nodes on a path from the root to a deepest node. The root alone has depth 1.

Function

maximumNaryDepth(parent: int[]) → int

Examples

Example 1

parent = [-1,0,0,1,1,3]return = 4

The deepest path is 0 -> 1 -> 3 -> 5.

Example 2

parent = [-1]return = 1

A one-node tree has depth one.

Example 3

parent = [4,4,0,0,-1,2]return = 4

The path 4 -> 0 -> 2 -> 5 has four nodes; parent indices need not precede children.

Constraints

  • 1 <= parent.length <= 100000.
  • Exactly one entry is -1.
  • Every other entry is a valid different node index.
  • The parent links form one rooted tree.

More Amazon problems

drafts saved locally
public int maximumNaryDepth(int[] parent) {
  // write your code here
}
parent[-1,0,0,1,1,3]
expected4
checking account