LeetCode Solutions Blog

Maximum Genetic Difference Query

Number: 2068

Difficulty: Hard

Paid? No

Companies: Media.net

Problem Description

Given a rooted tree where every node's label (from 0 to n - 1) also represents its unique genetic value, we are asked to handle multiple queries. Each query is in the form [node, val] and asks for the maximum value of (val XOR p) computed over every node p on the path from the given node to the root (inclusive). The tree is given via an array "parents", where parents[i] is the parent of node i (with the root having parents[root] == -1).

Key Insights

The tree is static but the queries are on different root-to-node paths.
A depth-first search (DFS) can be used to traverse the tree. We can "add" a node's value when entering it and "remove" it when backtracking.
A bitwise trie (prefix tree) is an efficient data structure to compute maximum XOR of a given number with the set of stored numbers.
Each DFS path simulates the current ancestors of a node, so queries anchored at that node can be answered via the current trie.
The trie must support insertion and removal to correctly maintain the current path's values.

Space and Time Complexity

Time Complexity: O((n + q) * B) where B is the number of bits needed (≈ 18-20), since each insertion, removal, and query operation on the trie costs O(B).
Space Complexity: O(n * B) in the worst case due to storage in the trie (in practice, the number of nodes in the trie is at most B * (nodes in path)).

Solution

We execute a DFS from the root of the tree while maintaining a bitwise trie that holds the genetic values of the current path (from root to the current node). When processing a node, we:

Insert its value into the trie.
Answer all queries related to this node by computing the maximum XOR of the query value with the values currently in the trie.
Recursively DFS into its children.
Remove its value from the trie as we backtrack.

The bitwise trie is implemented as a binary tree where each node has at most two children corresponding to bits 0 and 1. Insertion and removal work bit-by-bit (from the most significant bit to the least). The maximum XOR query chooses the opposite bit if available at each level to maximize the result.

Code Solutions

# Python solution

# Trie Node used for the bitwise trie
class TrieNode:
    def __init__(self):
        self.child = {}
        self.count = 0  # count of numbers passing through this node

class BitTrie:
    def __init__(self):
        self.root = TrieNode()
        # max_bit is chosen to support numbers up to around 2*10^5, so 18 bits is sufficient.
        self.max_bit = 18

    def insert(self, num):
        node = self.root
        for i in range(self.max_bit, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.child:
                node.child[bit] = TrieNode()
            node = node.child[bit]
            node.count += 1

    def remove(self, num):
        node = self.root
        for i in range(self.max_bit, -1, -1):
            bit = (num >> i) & 1
            next_node = node.child[bit]
            next_node.count -= 1
            if next_node.count == 0:
                # remove the node if no numbers pass through it
                del node.child[bit]
                return
            node = next_node

    def query(self, num):
        node = self.root
        if not node.child:
            return -1  # safe guard: should not happen as query is only when path exists
        max_xor = 0
        for i in range(self.max_bit, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            # choose the branch that gives higher XOR if present
            if toggled_bit in node.child:
                max_xor |= (1 << i)
                node = node.child[toggled_bit]
            else:
                node = node.child.get(bit, node)  # move on the same bit branch
        return max_xor

def maxGeneticDifference(parents, queries):
    n = len(parents)
    # Build tree: children list for each node
    tree = [[] for _ in range(n)]
    root = -1
    for i, p in enumerate(parents):
        if p == -1:
            root = i
        else:
            tree[p].append(i)
    
    # Map node -> list of (query_index, val)
    query_map = [[] for _ in range(n)]
    for qi, (node, val) in enumerate(queries):
        query_map[node].append((qi, val))
    
    answer = [0] * len(queries)
    trie = BitTrie()
    
    def dfs(node):
        # add current node value in the trie
        trie.insert(node)
        # answer all queries for current node
        for qi, val in query_map[node]:
            answer[qi] = trie.query(val)
        # visit children
        for child in tree[node]:
            dfs(child)
        # backtrack: remove current node value from trie
        trie.remove(node)
    
    dfs(root)
    return answer

# Example usage:
if __name__ == '__main__':
    parents = [-1, 0, 1, 1]
    queries = [[0, 2], [3, 2], [2, 5]]
    print(maxGeneticDifference(parents, queries))  # output: [2, 3, 7]