Maximum Genetic Difference Query - Solution & Explanation

Problem Overview: You are given a rooted tree where each node represents a genetic value equal to its index. For every query [node, val], compute the maximum val XOR x where x is any ancestor of node (including the node itself). The challenge is answering many XOR queries efficiently while traversing the tree.

Approach 1: DFS with Trie (Time: O((n + q) * logV), Space: O(n * logV))

This approach performs a depth-first search over the tree while maintaining a binary Trie of the values on the current root-to-node path. When DFS enters a node, insert the node's value into the Trie. For every query attached to that node, compute the maximum XOR with val by greedily choosing the opposite bit at each level of the Trie (a classic bit manipulation trick). After processing children, remove the node value when backtracking so the Trie always reflects the active ancestor path.

The key insight: at any moment during DFS, the Trie contains exactly the ancestors of the current node. That means each query becomes a standard "maximum XOR with set" operation. Since values are bounded by node indices, the Trie depth is about 18–20 bits, making each insert, delete, and query very fast.

Approach 2: Preprocessing with Persistent Trie (Time: O((n + q) * logV), Space: O(n * logV))

This approach builds a persistent binary Trie for each node representing the set of values from the root to that node. Instead of modifying a single Trie during DFS, every insertion creates a new version that shares most of its structure with the previous one. The version for a node is derived from its parent's version with the node value inserted.

Each query simply uses the persistent Trie version corresponding to the queried node and performs the same maximum XOR lookup. Because nodes share structure between versions, memory growth stays manageable while avoiding insert/remove operations during traversal.

The persistent structure is especially useful when queries are independent of traversal order or when you want immutable versions of the ancestor sets. The lookup process is identical to a standard maximum XOR search in a binary Trie.

Recommended for interviews: DFS with Trie is the approach most interviewers expect. It demonstrates understanding of tree traversal, dynamic data structures, and XOR optimization. The persistent Trie version shows deeper knowledge of functional data structures and is more common in competitive programming or advanced system design discussions.