FastPrepPreorder of Subtrees in an N-ary Tree
Problems/Preorder of Subtrees in an N-ary Tree

Preorder of Subtrees in an N-ary Tree

Nutanix logoNutanix● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Two reports from Nutanix's 2018 campus drive for a six-month internship plus a full-time offer list this as an online test question. You get a tree where a node can have many children, and a list of query nodes. For each query you give the preorder of that node's subtree. One report mentions up to 10^5 nodes and 10^5 queries.

The reports do not say how the tree is given or in what order to visit children. Here the tree comes as a parent array rooted at node 0, and children are visited from the smallest label to the largest. Every answer has to be returned in full. So there are at most 500 queries, and their subtrees hold at most 1500 nodes in total.

Our version is about 80% the same as the reported questions.

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^5
  • parent[0] == -1, and 0 <= parent[i] <= parent.length - 1 for every i >= 1
  • The parent array forms one tree rooted at node 0.
  • 1 <= queries.length <= 500
  • 0 <= 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

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int[][] subtreePreorders(int[] parent, int[] queries) {
        // Write your code here.
    }
}
Checking account…