Preorder of Subtrees in an N-ary Tree
Updated
Problem statement
A rooted tree has n nodes labeled from 0 to n - 1, and node 0 is the root. You are given an array parent of length n, where parent[0] = -1 and parent[i] is the parent of node i for every i >= 1. A node can have any number of children, and the children of each node are ordered by label, from smallest to largest.
You are also given an array queries. For each query node, list the nodes of its subtree in preorder: first the node itself, then the preorder of each child's subtree, one child after another in label order.
Return a list whose j-th entry is the preorder list for queries[j].
Function
subtreePreorders(parent: int[], queries: int[]) → int[][]Examples
Example 1
parent = [-1,0,0,1,1,2]queries = [1,0,5]return = [[1,3,4],[0,1,3,4,2,5],[5]]Node 0 has children 1 and 2, node 1 has children 3 and 4, and node 2 has child 5.
- The subtree of node 1 is visited as 1, then 3, then 4.
- The subtree of node 0 is the whole tree: 0, then the subtree of 1 (1, 3, 4), then the subtree of 2 (2, 5).
- Node 5 has no children, so its list is just
[5].
Example 2
parent = [-1,3,0,0,3]queries = [3,0,3]return = [[3,1,4],[0,2,3,1,4],[3,1,4]]Node 0 has children 2 and 3, and node 3 has children 1 and 4. Children are visited from the smallest label to the largest, so node 3 visits 1 before 4.
The subtree of node 3 is [3, 1, 4], and the whole tree from node 0 is [0, 2, 3, 1, 4]. Node 3 is asked twice, so its list appears twice.
Example 3
parent = [-1]queries = [0]return = [[0]]The tree has only node 0, so the only list is [0].
Constraints
1 <= parent.length <= 10^5parent[0] == -1, and0 <= parent[i] <= parent.length - 1for everyi >= 1- The parent array forms one tree rooted at node
0. 1 <= queries.length <= 5000 <= queries[j] <= parent.length - 1- The sizes of all queried subtrees add up to at most
1500.
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Count Prime Values in SubtreesVisa · OAVisa interview questions
- Part 1: The Narrowest KeyScale AI · OAScale AI interview questions
- Sewer Drainage PartitionTwo Sigma · OATwo Sigma interview questions
- Count Balanced Nodes in a Rooted TreeDRW · OADRW interview questions
- Chain of CommandIMC Trading · OAIMC Trading interview questions
- Construct Binary Tree S-ExpressionOptiver · OAOptiver interview questions
- Chain of CommandUber · OAUber interview questions
- Maximum Data Transfer TimeMicrosoft · OAMicrosoft interview questions
- Build and Render an Organization Role TreeStripe · OAStripe interview questions
- Kth Node in a Subtree DFSIntuit · OAIntuit interview questions