Input:I am provided with x and y.
x is a 32 bit non negative integer and y is some node-id of the tree.
So, I built a trie with 32-bit non negative integer values which are the keys associated with each node-id of the tree (DAG). Now, if I am asked to find the a node, whose key XOR x is maximum. This can be easily be done in O(log n) just by traversing the trie.
Now here is the extra condition:
I want to find the key on the node in the path from root to that node y, for which x XOR (key) is maximum. How can we find this out efficiently? Preferably in O(log n).