You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. Each node i has an integer value vals[i], and its parent is given by par[i].
The path XOR sum from the root to a node u is defined as the bitwise XOR of all vals[i] for nodes i on the path from the root node to node u, inclusive.
You are given a 2D integer array queries, where queries[j] = [uj, kj]. For each query, find the kjth smallest distinct path XOR sum among all nodes in the subtree rooted at uj. If there are fewer than kj distinct path XOR sums in that subtree, the answer is -1.
Return an integer array where the jth element is the answer to the jth query.
In a rooted tree, the subtree of a node v includes v and all nodes whose path to the root passes through v, that is, v and its descendants.
Example 1:
Input: par = [-1,0,0], vals = [1,1,1], queries = [[0,1],[0,2],[0,3]]
Output: [0,1,-1]
Explanation:
Path XORs:
11 XOR 1 = 01 XOR 1 = 0Subtree of 0: Subtree rooted at node 0 includes nodes [0, 1, 2] with Path XORs = [1, 0, 0]. The distinct XORs are [0, 1].
Queries:
queries[0] = [0, 1]: The 1st smallest distinct path XOR in the subtree of node 0 is 0.queries[1] = [0, 2]: The 2nd smallest distinct path XOR in the subtree of node 0 is 1.queries[2] = [0, 3]: Since there are only two distinct path XORs in this subtree, the answer is -1.Output: [0, 1, -1]
Example 2:
Input: par = [-1,0,1], vals = [5,2,7], queries = [[0,1],[1,2],[1,3],[2,1]]
Output: [0,7,-1,0]
Explanation:
Path XORs:
55 XOR 2 = 75 XOR 2 XOR 7 = 0Subtrees and Distinct Path XORs:
[0, 1, 2] with Path XORs = [5, 7, 0]. The distinct XORs are [0, 5, 7].[1, 2] with Path XORs = [7, 0]. The distinct XORs are [0, 7].[2] with Path XOR = [0]. The distinct XORs are [0].Queries:
queries[0] = [0, 1]: The 1st smallest distinct path XOR in the subtree of node 0 is 0.queries[1] = [1, 2]: The 2nd smallest distinct path XOR in the subtree of node 1 is 7.queries[2] = [1, 3]: Since there are only two distinct path XORs, the answer is -1.queries[3] = [2, 1]: The 1st smallest distinct path XOR in the subtree of node 2 is 0.Output: [0, 7, -1, 0]
Constraints:
1 <= n == vals.length <= 5 * 1040 <= vals[i] <= 105par.length == npar[0] == -10 <= par[i] < n for i in [1, n - 1]1 <= queries.length <= 5 * 104queries[j] == [uj, kj]0 <= uj < n1 <= kj <= npar represents a valid tree.Problem Overview: You are given a tree where each node contributes to a path XOR value. For every valid path considered in the problem, compute the XOR sum of its nodes and return the k-th smallest XOR value among all such paths.
Approach 1: Enumerate All Path XORs (Brute Force) (Time: O(n^2), Space: O(n^2))
The direct idea is to generate XOR values for every valid path and then pick the k-th smallest. Start a Depth-First Search from each node and maintain the current XOR while traversing. Every time you extend the path to a new node, update the running XOR and store it in an array. After collecting all path XOR values, sort the array and return the element at index k-1. This works but quickly becomes expensive because a tree with n nodes can generate up to O(n^2) paths.
Approach 2: DFS with Ordered Set / Size-K Structure (Time: O(n log k), Space: O(k))
A more scalable strategy avoids storing every path value. Traverse the tree once using DFS while maintaining the XOR value from the root to the current node. Each time a new path XOR is produced, insert it into an ordered set (or a max-heap) that keeps only the k smallest values seen so far. If the structure grows beyond size k, remove the largest element. This ensures the container always holds the smallest k XOR values discovered during traversal. After DFS completes, the largest value inside the structure represents the k-th smallest overall.
This technique works because you never need the full sorted list of path XORs. You only maintain the best k candidates while exploring the tree. Insertions and removals take O(log k) time, which keeps the traversal efficient even for large inputs.
The algorithm relies heavily on tree traversal and prefix-style XOR accumulation. If the node values are stored in an array, computing the next XOR is a constant-time operation during DFS expansion.
Recommended for interviews: Interviewers expect you to first recognize that brute-force path enumeration is too slow. Explaining the O(n^2) idea shows understanding of path generation in trees. The optimized DFS with a bounded ordered structure demonstrates practical optimization and awareness of time–space tradeoffs, which is typically the solution they want.
Python
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumerate All Path XORs | O(n^2) | O(n^2) | Small trees or when path count is limited and simplicity is preferred |
| DFS + Ordered Set / Heap (Top K) | O(n log k) | O(k) | General case where the number of paths is large but only the kth smallest value is required |
3590. Kth Smallest Path XOR Sum | Biweekly Contest 159 • Amit Dhyani • 765 views views
Watch 2 more video solutions →Practice Kth Smallest Path XOR Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor