3590. Kth Smallest Path XOR Sum

HardTreeDepth-First SearchArrayOrdered Set

Problem Description

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] = [u_j, k_j]. For each query, find the k_j-th smallest distinct path XOR sum among all nodes in the subtree rooted at u_j. If there are fewer than k_j distinct path XOR sums in that subtree, the answer is -1.

Return an integer array where the j-th element is the answer to the j-th 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To answer queries about the k-th smallest distinct path XOR sum within a subtree, first observe that the XOR value from the root to each node can be easily computed by traversing the tree and propagating the XOR from parent to child. Each subtree corresponds to a collection of these XOR values, gathered from the node itself and all its descendants.

Since we need to efficiently collect all distinct XOR values for arbitrary subtrees and then find the k-th smallest, a naive approach of collecting and sorting values for each query would be too slow. Instead, we can use a mergeset technique while traversing the tree: at each node, maintain a set of distinct XOR values in its subtree by merging its children's sets into its own.

To answer "k-th smallest" efficiently, instead of a typical set, we use a binary trie data structure. This allows us to insert, merge, and search for the k-th smallest efficiently. As we perform a depth-first search, we collect all path XORs in the binary trie for each subtree, and use this trie to directly answer the queries on that node.

This approach leverages path properties and efficient data structure merging to handle potentially large trees and many queries within acceptable time limits.

Solution Approach

The solution computes, for each query, the k-th smallest distinct path XOR sum within the subtree rooted at a given node. The core parts of the approach are:

Preprocessing XOR Paths:
- For each node, we first compute its path XOR sum from the root.
- We do this using depth-first search (DFS). For each node, its path XOR is the XOR of its value and its parent's path XOR.
Handling Subtree Queries:
- Each query asks about the subtree rooted at some node u.
- For each node, we want to quickly know all the distinct path XOR sums in its subtree (including itself).
Efficient Distinct Collection via Tries:
- To handle merging sets of XOR path sums from different subtrees efficiently, we use a binary trie (BinarySumTrie).
- Every node's trie holds the XOR path sums in its subtree.
- Adding and merging with a trie is fast and lets us answer k-th smallest queries quickly.
DFS with Trie Merging:
- We run a DFS from the root:
  - For each child, perform DFS recursively.
  - After processing a child, merge its trie into the current node's trie.
  - To optimize, always merge the smaller trie into the bigger trie, reducing total operations.
  - When merging, we insert all values from the child trie to the parent trie only if they aren't already present.
- At each node, after merging, the trie contains all distinct path XORs in its subtree.
Query Answering:
- Each query is attached to the corresponding u.
- After processing a node (when all merges are done), if there are at least k distinct elements in its trie, we use the trie to retrieve the k-th smallest value (using the find_kth method).
- Otherwise, return -1.

Summary:

The main data structure is a binary trie which allows log-scale insert/search operations and efficient merge of sets.
The solution processes the tree in a bottom-up fashion using DFS, merging subtrees, and answering subtree-specific queries as we return from the calls.

This approach efficiently computes and merges the required information, ensuring that each operation is fast enough to handle large trees and many queries.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's work through a small example to clarify the approach:

Suppose we have the following tree with 5 nodes:

vals = [4, 6, 7, 1, 3]
par = [-1, 0, 0, 2, 2]
queries = [[0, 3], [2, 2], [2, 5], [3, 1]]
- For each [u, k], look for the k-th smallest distinct path XOR in the subtree rooted at u.

Step 1: Precompute path XORs

node 0: path = [0], path XOR = 4
node 1: path = [0,1], path XOR = 4 ^ 6 = 2
node 2: path = [0,2], path XOR = 4 ^ 7 = 3
node 3: path = [0,2,3],path XOR = 4 ^ 7 ^ 1 = 2
node 4: path = [0,2,4],path XOR = 4 ^ 7 ^ 3 = 0

So, the path XORs for each node:

0: 4
1: 2
2: 3
3: 2
4: 0

Step 2: Gather subtree XORs and answer queries

Build the tree and assign queries by node:

Queries at node 0: [0, 3]
Queries at node 2: [2, 2], [2, 5]
Queries at node 3: [3, 1]

DFS traversal with trie merging:

At leaf 1: Only itself (path XOR = 2). Trie = {2}
At leaf 3: Only itself (path XOR = 2). Trie = {2}
- Query [3,1]: 1st smallest = 2
At leaf 4: Only itself (path XOR = 0). Trie = {0}
At node 2:
- Itself: 3
- Leaves: 3 (from this node) + 2 (from 3) + 0 (from 4)
- Merged Trie = {0, 2, 3}
- Query [2,2]: 2nd smallest = 2
- Query [2,5]: only 3 distinct, so 5th smallest = -1
At root 0:
- Itself: 4
- Trie from 1: {2}
- Trie from 2 subtree: {0, 2, 3}
- Merge all: {0, 2, 3, 4}
- Query [0,3]: 3rd smallest = 3

Summary of query answers:

[0, 3] → 3 (the 3rd smallest in {0,2,3,4} is 3)
[2, 2] → 2 (the 2nd smallest in {0,2,3} is 2)
[2, 5] → -1 (only 3 distinct, no 5th smallest)
[3, 1] → 2 (only one value: 2)

Conclusion

The method computes path XORs, builds tries as subtrees are processed, merges them efficiently, then answers each query in place using the constructed trie.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4class BinarySumTrie:
5    def __init__(self):
6        # Number of elements in the subtrie
7        self.count = 0
8        # Left (0) and right (1) children
9        self.children = [None, None]
10
11    def add(self, num: int, delta: int, bit: int = 17):
12        """
13        Insert or delete a number into the Trie.
14        delta: +1 for insert, -1 for delete
15        """
16        self.count += delta
17        if bit < 0:
18            return
19        b = (num >> bit) & 1
20        if not self.children[b]:
21            self.children[b] = BinarySumTrie()
22        self.children[b].add(num, delta, bit - 1)
23
24    def collect(self, prefix: int = 0, bit: int = 17, output: List[int] = None):
25        """
26        Collect all numbers stored in the Trie, in lexicographical order.
27        """
28        if output is None:
29            output = []
30        if self.count == 0:
31            return output
32        if bit < 0:
33            output.append(prefix)
34            return output
35        if self.children[0]:
36            self.children[0].collect(prefix, bit - 1, output)
37        if self.children[1]:
38            self.children[1].collect(prefix | (1 << bit), bit - 1, output)
39        return output
40
41    def exists(self, num: int, bit: int = 17) -> bool:
42        """
43        Check if a number exists in the Trie.
44        """
45        if self.count == 0:
46            return False
47        if bit < 0:
48            return True
49        b = (num >> bit) & 1
50        if not self.children[b]:
51            return False
52        return self.children[b].exists(num, bit - 1)
53
54    def find_kth(self, k: int, bit: int = 17) -> int:
55        """
56        Find the k-th smallest number in the Trie.
57        Returns -1 if not enough elements.
58        """
59        if k > self.count:
60            return -1
61        if bit < 0:
62            return 0
63        left_count = self.children[0].count if self.children[0] else 0
64        if k <= left_count:
65            return self.children[0].find_kth(k, bit - 1)
66        if self.children[1]:
67            right_result = self.children[1].find_kth(k - left_count, bit - 1)
68            if right_result != -1:
69                return (1 << bit) | right_result
70        return -1
71
72
73class Solution:
74    def kthSmallest(
75        self, par: List[int], vals: List[int], queries: List[List[int]]
76    ) -> List[int]:
77        n = len(par)
78        tree = [[] for _ in range(n)]  # Build the adjacency list for the tree
79
80        # Build the tree structure
81        for i in range(1, n):
82            tree[par[i]].append(i)
83
84        path_xor = vals[:]
85
86        def compute_xor(node: int, acc: int):
87            """
88            Use DFS to compute path XOR from root to each node.
89            """
90            path_xor[node] ^= acc
91            for child in tree[node]:
92                compute_xor(child, path_xor[node])
93
94        compute_xor(0, 0)
95
96        # Group queries by node for efficient processing
97        node_queries = defaultdict(list)
98        for idx, (u, k) in enumerate(queries):
99            node_queries[u].append((k, idx))
100
101        trie_at_node = {}
102        result = [0] * len(queries)
103
104        def dfs(node: int):
105            """
106            DFS traversal to build prefix tries at each node and answer queries.
107            """
108            # Create a new Trie for this node with just its path_xor value
109            trie_at_node[node] = BinarySumTrie()
110            trie_at_node[node].add(path_xor[node], 1)
111            # Merge the Tries from all children into this node's Trie
112            for child in tree[node]:
113                dfs(child)
114                # Always merge smaller trie into larger for efficiency
115                if trie_at_node[node].count < trie_at_node[child].count:
116                    trie_at_node[node], trie_at_node[child] = trie_at_node[child], trie_at_node[node]
117                # Add all unique values from child Trie into current Trie
118                for val in trie_at_node[child].collect():
119                    if not trie_at_node[node].exists(val):
120                        trie_at_node[node].add(val, 1)
121            # Answer each query for this node
122            for k, idx in node_queries[node]:
123                if trie_at_node[node].count < k:
124                    result[idx] = -1
125                else:
126                    result[idx] = trie_at_node[node].find_kth(k)
127
128        dfs(0)
129        return result
130

1import java.util.*;
2
3class BinarySumTrie {
4    // Number of elements in the subtree rooted at this node
5    int count;
6    // Children: children[0] for bit 0, children[1] for bit 1
7    BinarySumTrie[] children;
8
9    public BinarySumTrie() {
10        this.count = 0;
11        this.children = new BinarySumTrie[2];
12    }
13
14    // Insert or delete a number from the trie, delta = +1 for insertion, -1 for deletion
15    public void add(int num, int delta, int bit) {
16        this.count += delta;
17        if (bit < 0) {
18            return;
19        }
20        int b = (num >> bit) & 1;
21        if (this.children[b] == null) {
22            this.children[b] = new BinarySumTrie();
23        }
24        this.children[b].add(num, delta, bit - 1);
25    }
26
27    // Collect all numbers in the trie in lexicographical order
28    public void collect(int prefix, int bit, List<Integer> output) {
29        if (this.count == 0) {
30            return;
31        }
32        if (bit < 0) {
33            output.add(prefix);
34            return;
35        }
36        if (this.children[0] != null) {
37            this.children[0].collect(prefix, bit - 1, output);
38        }
39        if (this.children[1] != null) {
40            this.children[1].collect(prefix | (1 << bit), bit - 1, output);
41        }
42    }
43
44    // Check if a number exists in the trie
45    public boolean exists(int num, int bit) {
46        if (this.count == 0) {
47            return false;
48        }
49        if (bit < 0) {
50            return true;
51        }
52        int b = (num >> bit) & 1;
53        if (this.children[b] == null) {
54            return false;
55        }
56        return this.children[b].exists(num, bit - 1);
57    }
58
59    // Find the k-th smallest number in the trie. Returns -1 if not enough elements.
60    public int findKth(int k, int bit) {
61        if (k > this.count) {
62            return -1;
63        }
64        if (bit < 0) {
65            return 0;
66        }
67        int leftCount = (this.children[0] != null) ? this.children[0].count : 0;
68        if (k <= leftCount) {
69            return this.children[0].findKth(k, bit - 1);
70        }
71        if (this.children[1] != null) {
72            int rightResult = this.children[1].findKth(k - leftCount, bit - 1);
73            if (rightResult != -1) {
74                return (1 << bit) | rightResult;
75            }
76        }
77        return -1;
78    }
79}
80
81class Solution {
82    public int[] kthSmallest(int[] par, int[] vals, int[][] queries) {
83        int n = par.length;
84        List<Integer>[] tree = new ArrayList[n];
85
86        // Build the adjacency list for the tree
87        for (int i = 0; i < n; i++) {
88            tree[i] = new ArrayList<>();
89        }
90        for (int i = 1; i < n; i++) {
91            tree[par[i]].add(i);
92        }
93
94        // Compute the path XOR for each node
95        int[] pathXor = Arrays.copyOf(vals, n);
96
97        // DFS to compute the XOR from root to each node
98        computeXor(0, 0, tree, pathXor);
99
100        // Group queries by node for efficient processing
101        Map<Integer, List<int[]>> nodeQueries = new HashMap<>();
102        for (int i = 0; i < queries.length; i++) {
103            int u = queries[i][0];
104            int k = queries[i][1];
105            nodeQueries.computeIfAbsent(u, key -> new ArrayList<>()).add(new int[]{k, i});
106        }
107
108        BinarySumTrie[] trieAtNode = new BinarySumTrie[n];
109        int[] result = new int[queries.length];
110
111        // DFS to build tries and answer queries
112        dfs(0, tree, pathXor, nodeQueries, trieAtNode, result);
113
114        return result;
115    }
116
117    // Helper DFS to compute path XOR
118    private void computeXor(int node, int acc, List<Integer>[] tree, int[] pathXor) {
119        pathXor[node] ^= acc;
120        for (int child : tree[node]) {
121            computeXor(child, pathXor[node], tree, pathXor);
122        }
123    }
124
125    // DFS traversal to build tries and answer queries
126    private void dfs(
127        int node,
128        List<Integer>[] tree,
129        int[] pathXor,
130        Map<Integer, List<int[]>> nodeQueries,
131        BinarySumTrie[] trieAtNode,
132        int[] result
133    ) {
134        // New trie for this node, insert its path xor value
135        trieAtNode[node] = new BinarySumTrie();
136        trieAtNode[node].add(pathXor[node], 1, 17);
137
138        // Merge child tries into current trie
139        for (int child : tree[node]) {
140            dfs(child, tree, pathXor, nodeQueries, trieAtNode, result);
141
142            // Always merge smaller trie into larger one for efficiency
143            if (trieAtNode[node].count < trieAtNode[child].count) {
144                BinarySumTrie temp = trieAtNode[node];
145                trieAtNode[node] = trieAtNode[child];
146                trieAtNode[child] = temp;
147            }
148
149            // Merge values from child trie
150            List<Integer> valsToAdd = new ArrayList<>();
151            trieAtNode[child].collect(0, 17, valsToAdd);
152            for (int val : valsToAdd) {
153                if (!trieAtNode[node].exists(val, 17)) {
154                    trieAtNode[node].add(val, 1, 17);
155                }
156            }
157        }
158
159        // Answer queries for this node
160        if (nodeQueries.containsKey(node)) {
161            for (int[] query : nodeQueries.get(node)) {
162                int k = query[0];
163                int idx = query[1];
164                if (trieAtNode[node].count < k) {
165                    result[idx] = -1;
166                } else {
167                    result[idx] = trieAtNode[node].findKth(k, 17);
168                }
169            }
170        }
171    }
172}
173

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5using namespace std;
6
7// Trie for representing numbers in binary and supporting insert, delete, kth smallest etc.
8class BinarySumTrie {
9public:
10    int count; // Number of elements in the subtrie
11    BinarySumTrie* children[2];
12
13    BinarySumTrie() : count(0) {
14        children[0] = children[1] = nullptr;
15    }
16
17    // Insert or delete a number into the Trie. delta: +1 for insert, -1 for delete
18    void add(int num, int delta, int bit = 17) {
19        count += delta;
20        if (bit < 0) return;
21        int b = (num >> bit) & 1;
22        if (!children[b])
23            children[b] = new BinarySumTrie();
24        children[b]->add(num, delta, bit - 1);
25    }
26
27    // Collect all numbers stored in the Trie, in lexicographical order.
28    void collect(int prefix, int bit, vector<int>& output) {
29        if (count == 0)
30            return;
31        if (bit < 0) {
32            output.push_back(prefix);
33            return;
34        }
35        if (children[0])
36            children[0]->collect(prefix, bit - 1, output);
37        if (children[1])
38            children[1]->collect(prefix | (1 << bit), bit - 1, output);
39    }
40
41    // Check if a number exists in the Trie.
42    bool exists(int num, int bit = 17) {
43        if (count == 0)
44            return false;
45        if (bit < 0)
46            return true;
47        int b = (num >> bit) & 1;
48        if (!children[b])
49            return false;
50        return children[b]->exists(num, bit - 1);
51    }
52
53    // Find the k-th smallest number in the Trie.
54    // Returns -1 if there aren't enough elements.
55    int find_kth(int k, int bit = 17) {
56        if (k > count)
57            return -1;
58        if (bit < 0)
59            return 0;
60        int left_count = (children[0] ? children[0]->count : 0);
61        if (k <= left_count)
62            return (children[0] ? children[0]->find_kth(k, bit - 1) : -1);
63        if (children[1]) {
64            int right_result = children[1]->find_kth(k - left_count, bit - 1);
65            if (right_result != -1)
66                return (1 << bit) | right_result;
67        }
68        return -1;
69    }
70
71    // Destructor to release memory
72    ~BinarySumTrie() {
73        if (children[0]) delete children[0];
74        if (children[1]) delete children[1];
75    }
76};
77
78class Solution {
79public:
80    vector<int> kthSmallest(
81        vector<int>& par, vector<int>& vals, vector<vector<int>>& queries) {
82
83        int n = par.size();
84        vector<vector<int>> tree(n); // Tree adjacency list
85        for (int i = 1; i < n; ++i) {
86            tree[par[i]].push_back(i);
87        }
88
89        vector<int> path_xor = vals;
90
91        // DFS to compute path xor from root to each node
92        function<void(int, int)> compute_xor = [&](int node, int acc) {
93            path_xor[node] ^= acc;
94            for (int child : tree[node]) {
95                compute_xor(child, path_xor[node]);
96            }
97        };
98
99        compute_xor(0, 0);
100
101        // Group queries by node for efficient processing
102        unordered_map<int, vector<pair<int, int>>> node_queries;
103        for (int i = 0; i < queries.size(); ++i) {
104            int u = queries[i][0];
105            int k = queries[i][1];
106            node_queries[u].emplace_back(k, i);
107        }
108
109        vector<BinarySumTrie*> trie_at_node(n, nullptr);
110        vector<int> result(queries.size(), 0);
111
112        // DFS traversal to build prefix tries at each node and answer queries.
113        function<void(int)> dfs = [&](int node) {
114            // Create a new Trie for this node with just its path_xor value
115            trie_at_node[node] = new BinarySumTrie();
116            trie_at_node[node]->add(path_xor[node], 1);
117
118            // Merge the tries from all children into this node's trie
119            for (int child : tree[node]) {
120                dfs(child);
121                // Always merge smaller trie into larger for efficiency
122                if (trie_at_node[node]->count < trie_at_node[child]->count) {
123                    swap(trie_at_node[node], trie_at_node[child]);
124                }
125                // Add all unique values from child trie into current trie
126                vector<int> values;
127                trie_at_node[child]->collect(0, 17, values);
128                for (int val : values) {
129                    if (!trie_at_node[node]->exists(val))
130                        trie_at_node[node]->add(val, 1);
131                }
132            }
133
134            // Answer each query for this node
135            if (node_queries.count(node)) {
136                for (auto& q : node_queries[node]) {
137                    int k = q.first, idx = q.second;
138                    if (trie_at_node[node]->count < k) {
139                        result[idx] = -1;
140                    } else {
141                        result[idx] = trie_at_node[node]->find_kth(k);
142                    }
143                }
144            }
145        };
146
147        dfs(0);
148
149        // Clean up Trie memory
150        for (auto t : trie_at_node)
151            if (t) delete t;
152
153        return result;
154    }
155};
156

1// Utility for a binary trie node to store numbers in bitwise representation
2type TrieNode = {
3    count: number, // Number of elements in the subtrie
4    children: [TrieNode | null, TrieNode | null] // Left (0) and right (1) children
5}
6
7// Create a new trie node
8function createTrieNode(): TrieNode {
9    return { count: 0, children: [null, null] };
10}
11
12// Insert or delete a number in the binary trie
13function trieAdd(root: TrieNode, num: number, delta: number, bit: number = 17): void {
14    root.count += delta;
15    if (bit < 0) return;
16    const b = (num >> bit) & 1;
17    if (!root.children[b]) root.children[b] = createTrieNode();
18    trieAdd(root.children[b]!, num, delta, bit - 1);
19}
20
21// Collects all numbers in trie, in lexicographical order
22function trieCollect(root: TrieNode, prefix: number = 0, bit: number = 17, output: number[] = []): number[] {
23    if (root.count === 0) return output;
24    if (bit < 0) {
25        output.push(prefix);
26        return output;
27    }
28    if (root.children[0]) trieCollect(root.children[0], prefix, bit - 1, output);
29    if (root.children[1]) trieCollect(root.children[1], prefix | (1 << bit), bit - 1, output);
30    return output;
31}
32
33// Checks if a number exists in the trie
34function trieExists(root: TrieNode, num: number, bit: number = 17): boolean {
35    if (root.count === 0) return false;
36    if (bit < 0) return true;
37    const b = (num >> bit) & 1;
38    if (!root.children[b]) return false;
39    return trieExists(root.children[b]!, num, bit - 1);
40}
41
42// Find the k-th smallest number in the Trie; returns -1 if out of range
43function trieFindKth(root: TrieNode, k: number, bit: number = 17): number {
44    if (k > root.count) return -1;
45    if (bit < 0) return 0;
46    const leftCount = root.children[0]?.count ?? 0;
47    if (k <= leftCount) return trieFindKth(root.children[0]!, k, bit - 1);
48    if (root.children[1]) {
49        const rightResult = trieFindKth(root.children[1], k - leftCount, bit - 1);
50        if (rightResult !== -1) return (1 << bit) | rightResult;
51    }
52    return -1;
53}
54
55// Main function to process path xor tree queries
56function kthSmallest(par: number[], vals: number[], queries: number[][]): number[] {
57    const n = par.length;
58    const tree: number[][] = Array.from({ length: n }, () => []);
59
60    // Build adjacency list for the tree
61    for (let i = 1; i < n; ++i) {
62        tree[par[i]].push(i);
63    }
64
65    const pathXor = vals.slice();
66    // Compute path XOR for every node using DFS
67    function computeXor(node: number, acc: number): void {
68        pathXor[node] ^= acc;
69        for (const child of tree[node]) {
70            computeXor(child, pathXor[node]);
71        }
72    }
73    computeXor(0, 0);
74
75    // Group queries per node for efficient retrieval
76    const nodeQueries: Map<number, Array<[number, number]>> = new Map();
77    for (let i = 0; i < queries.length; ++i) {
78        const [u, k] = queries[i];
79        if (!nodeQueries.has(u)) nodeQueries.set(u, []);
80        nodeQueries.get(u)!.push([k, i]);
81    }
82
83    // Store a trie at every node
84    const trieAtNode: Map<number, TrieNode> = new Map();
85    const result: number[] = Array(queries.length);
86
87    // DFS traversal to merge subtrees and compute answers
88    function dfs(node: number): void {
89        // Create a trie for current node, and add the current node's xor path
90        trieAtNode.set(node, createTrieNode());
91        trieAdd(trieAtNode.get(node)!, pathXor[node], 1);
92
93        // Merge tries from all children into current node's trie
94        for (const child of tree[node]) {
95            dfs(child);
96            const nodeTrie = trieAtNode.get(node)!;
97            const childTrie = trieAtNode.get(child)!;
98            // Always merge smaller into larger for efficiency
99            if (nodeTrie.count < childTrie.count) {
100                trieAtNode.set(node, childTrie);
101                trieAtNode.set(child, nodeTrie);
102            }
103            // Add all unique values from child into the current node's trie
104            for (const val of trieCollect(trieAtNode.get(child)!)) {
105                if (!trieExists(trieAtNode.get(node)!, val)) {
106                    trieAdd(trieAtNode.get(node)!, val, 1);
107                }
108            }
109        }
110
111        // Answer any queries for this node
112        if (nodeQueries.has(node)) {
113            for (const [k, idx] of nodeQueries.get(node)!) {
114                const trie = trieAtNode.get(node)!;
115                if (trie.count < k) {
116                    result[idx] = -1;
117                } else {
118                    result[idx] = trieFindKth(trie, k);
119                }
120            }
121        }
122    }
123    dfs(0);
124    return result;
125}
126

Time and Space Complexity

Time Complexity:

Let n be the number of nodes, q the number of queries, and B the maximum number of bits (here, B = 18, since the trie uses bit=17).

Each node has a BinarySumTrie storing all unique path_xor values in its subtree.
Merging tries (DSU on tree):
- Each node's trie is merged with its children's tries by traversing all values once per edge, performing add/exist.
- Over the entire tree, each insertion and merge happens logarithmically for each distinct value across all subtrees.
- The total number of operations over all merges is O(n * B)—each of the n nodes is inserted/merged into at most B trie nodes (one per bit).
Querying:
- Each query on a trie (find_kth) is O(B).
- There are q queries, so total query time is O(q * B).

Final total time complexity:

O((n + q) * B)

where B = 18.

Space Complexity:

Each node can contain up to its subtree size worth of distinct values in its trie.
However, due to merges, at most O(n) BinarySumTrie nodes exist and each node may have up to 2 children per bit, so:
For all nodes, size is O(n * B) for BinarySumTrie nodes.
Result array and data structures for input are O(n + q).

Final total space complexity:

O(n * B + q)

where B = 18.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know