3590. Kth Smallest Path XOR Sum
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.
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).
- Each query asks about the subtree rooted at some node
-
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.
- To handle merging sets of XOR path sums from different subtrees efficiently, we use a binary trie (
-
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.
- We run a DFS from the root:
-
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 thefind_kth
method). - Otherwise, return
-1
.
- Each query is attached to the corresponding
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 EvaluatorExample Walkthrough
Let's work through a small example to clarify the approach:
Suppose we have the following tree with 5 nodes:
0 / \ 1 2 / \ 3 4
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.
- For each
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
- Query
- 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 uniquepath_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 then
nodes is inserted/merged into at mostB
trie nodes (one per bit).
- Querying:
- Each query on a trie (find_kth) is
O(B)
. - There are
q
queries, so total query time isO(q * B)
.
- Each query on a trie (find_kth) is
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)
forBinarySumTrie
nodes. - Result array and data structures for input are
O(n + q)
.
Final total space complexity:
O(n * B + q)
where B = 18
.
How many times is a tree node visited in a depth first search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!