Find a Node’s Level in an N-ary Tree
Updated
Problem statement
Find the level of targetId in an N-ary tree, where the root has level 0 and each child has its parent’s level plus 1. Return -1 if the ID is absent.
For this exercise, the tree is represented by two parallel arrays. nodeIds[i] is the unique ID of node at index i. children[i] lists the indices of that node’s children. The root is at index 0 when the arrays are nonempty. Child entries are array indices, while targetId is a node ID; do not confuse the two.
The input is guaranteed to form a valid rooted tree: every non-root node has exactly one parent and is reachable from the root, and there are no cycles or repeated child links. An empty tree returns -1. Leave both arrays unchanged.
Function
nodeLevel(nodeIds: int[], children: int[][], targetId: int) → intExamples
Example 1
nodeIds = [10,20,30,40,50]children = [[1,2],[3,4],[],[],[]]targetId = 40return = 2Root ID 10 is at level 0. Its child ID 20 is at level 1, and ID 40 is a child of ID 20, so ID 40 is at level 2. Child lists contain indices, such as index 3 for ID 40.
Example 2
nodeIds = [10,20,30,40,50]children = [[1,2],[3,4],[],[],[]]targetId = 999return = -1The same valid tree has IDs 10,20,30,40,50. ID 999 is absent, so the result is -1.
Constraints
- For this exercise, assume 0 <= nodeIds.length <= 500.
- For this exercise, assume 0 <= children.length <= 500.
- nodeIds and children have equal length.
- Every node ID is between 1 and 1000000, inclusive.
- All node IDs are distinct.
- For this exercise, assume 0 <= targetId <= 1000000.
- Every children row has at most 499 indices.
- Every child index is between 0 and 499, inclusive.
- For nonempty input, children describes a valid rooted N-ary tree at index 0: every child index is less than nodeIds.length, every other node has exactly one parent and is reachable from the root, and there are no cycles or repeated child links.
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)