FastPrepK-th Ancestor Subtree Preorder Query
Problems/K-th Ancestor Subtree Preorder Query

K-th Ancestor Subtree Preorder Query

Adobe logoAdobe● HardNEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The source omits bounds and a callable return format; the accompanying solution establishes the root and traversal order. The judged core task matches the visible report at about 97%.

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]:

  1. Find the k-th ancestor of node u, where the 0-th ancestor is u itself.
  2. If that ancestor does not exist, return the one-element row [-1].
  3. 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.

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
class Solution {
    public int[][] subtreeValuesAfterAncestor(int[] values, int[][] edges, int[][] queries) {
        // Write your solution here
    }
}
Checking account…