K-th Ancestor Subtree Preorder Query
Reported by candidates from Adobe's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Adobe reported this one in August 2026, and the detail that trips people is in the second example: node 1 visits child 3 before child 2 because edge [1, 3] shows up first in the list. Child order follows edge order, not node number. The problem is a rooted tree with k-th ancestor queries, then a preorder dump of that ancestor's subtree. With n and queries both up to 2 * 10^5, brute force dies. StealthCoder is there as a hedge if you blank on the live OA, but the pattern is short once you see it.
The problem
You are given a tree with nodes numbered from 1 to n. Node i stores values[i - 1]. The tree is rooted at node 1. The undirected edges are processed in their given order. After rooting the tree, each node's children are visited in the order in which their incident edges first appear in edges. For each query [u, k]: Find the k-th ancestor of node u, where the 0-th ancestor is u itself. If that ancestor does not exist, return the one-element row [-1]. Otherwise, return the values in that ancestor's subtree in preorder. Return one result row for each query, preserving query order. Function subtreeValuesAfterAncestor(values: int[], edges: int[][], queries: int[][]) → int[][] Examples Example 1 values = [10, 20, 30, 40, 50] edges = [[1, 2], [1, 3], [2, 4], [2, 5]] queries = [[4, 1], [4, 2], [3, 0], [1, 1]] return = [[20, 40, 50], [10, 20, 40, 50, 30], [30], [-1]] The first query reaches node 2 and returns its preorder subtree. The second reaches root 1. The third keeps node 3, and the root has no first ancestor for the last query. Example 2 values = [1, 2, 3, 4] edges = [[2, 4], [1, 3], [1, 2]] queries = [[4, 1], [4, 2]] return = [[2, 4], [1, 3, 2, 4]] Node 1 visits child 3 before child 2 because edge [1, 3] appears earlier than [1, 2]. Node 2 then visits node 4. Constraints 1 <= n == values.length <= 2 * 10^5 -10^9 <= values[i] <= 10^9 edges.length == n - 1 edges describes one valid tree on nodes 1 through n. 1 <= queries.length <= 2 * 10^5 1 <= u <= n 0 <= k <= n The total number of values returned across all successful queries is at most 2 * 10^5.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Do one iterative DFS from node 1, visiting children in the order their edges first appear in the input. Record the preorder array, each node's tin (index in preorder), and subtree size. Then any subtree's preorder is just a contiguous slice: order[tin[a] : tin[a] + size[a]]. For k-th ancestor, use binary lifting (up[j][v], log n about 18 levels), or answer offline using the DFS stack depth. If k exceeds depth, return [-1]. The constraint that total returned values is at most 2 * 10^5 means slicing is safe. Pitfalls: recursion depth on a path-shaped tree, so go iterative. Also don't sort adjacency lists by node id. Build adjacency by appending in edge order and the order comes free. If you freeze live, StealthCoder can supply the skeleton while you check the edge-order rule.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill K-th Ancestor Subtree Preorder Query cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Adobe's OA.
Adobe reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
K-th Ancestor Subtree Preorder Query FAQ
What's the trick in this Adobe K-th Ancestor Subtree Preorder problem?+
Preorder of a subtree is a contiguous slice of the global preorder array. Compute tin and subtree size once with one DFS, then each query is a k-th ancestor lookup plus a slice. No per-query traversal needed.
How do I find the k-th ancestor fast enough?+
Binary lifting works: build up[j][v] for powers of two, then decompose k into bits. That's O(n log n) build and O(log n) per query. If k is greater than n or the jump hits zero, return [-1]. Offline with a DFS stack also works.
How should I order children?+
By the order their edges first appear in the edges array. Append neighbors to adjacency lists as you read edges, then DFS from node 1 skipping the parent. Don't sort by node number. Example 2 exists to catch exactly that mistake.
Will recursion break on this problem?+
Yes, likely. n goes to 2 * 10^5 and a chain-shaped tree gives that depth. Use an explicit stack for DFS. In Python especially, recursion limits will bite you. Push children in reverse order so they pop in the correct edge order.
How do I prepare for this in 48 hours?+
Practice three pieces: iterative DFS with tin and size, binary lifting for k-th ancestor, and slicing output. Write each from memory once. Test on both examples, then on a chain and a star. Edge cases are k=0, k beyond depth, and the root.