Kth Node in a Subtree DFS
Updated
Problem statement
A rooted tree has nodes 1..n, with root 1. parents[v-1] is the parent of node v; parents[0] is zero. Children are visited in ascending node-ID order. Each query [u,k] asks for the kth node in a preorder DFS that starts at u and visits its descendants. The starting node is first. Return -1 when the subtree has fewer than k nodes.
Function
kthSubtreeNodes(parents: int[], queries: int[][]) → int[]Examples
Example 1
parents = [0,1,1,2,2,3]queries = [[1,1],[1,4],[2,3],[3,3]]return = [1,5,5,-1]The root traversal is 1,2,4,5,3,6.
Example 2
parents = [0]queries = [[1,1],[1,2]]return = [1,-1]The one-node subtree has only rank one.
Constraints
- For this exercise, assume a valid rooted tree, 1 <= n <= 100000, queries.length <= 100000, valid node IDs, and 1 <= k <= 10^9.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
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
- Best Sum Downward Tree PathCitadel · OACitadel interview questions