3

Basically you have a BST filled with values. eg. 1-16 a min,max and value (10,15,3) and you need to find the maximum xor value between the values in the BST and the given value that are within min and max of the tree.

I'm wondering if there is a way to do this without iterating throughout the entire tree. if min and max didn't exist, my approach would be.

int xor (Node curent,min,max,value,highestXor){
 1. if node == null return highestXor
 2. check node.value ^ value, if > highestXor replace.
 3. check node.left ^ value and node.right ^ value, nextNode= highest between them 
 4. xor(nextNode,min,max,value,newHighest)
}

Basically keep following the nodes which produce higher xor values.

The problem i'm running into with min and max is, when I place the checks for node>=min && node<=max the tree will traverse fine, but when i'm within range, it's possible that I may be taking a bad branch to a number outside of the range.

Let me explain. Take this right side of a BST 1-16

      9 
    /   \
  /       \
5           13
           /   \
         11     15
         /\     /\
       10  12 14  16

given:

  • min = 10
  • max = 15
  • value = 3

The maximum Xor value is 3^12=15

However with my algorithm, when i'm at the 13 node, instead of taking the left tree to 11, i'm taking the right tree to 15 (because it's trying to get to 16 but thats out of range).

Does anyone have a better solution? should I be sorting my BST differently? Should I be using something instead of a BST? Is it possible to do this without traversing the entire list of values? The assumption here is that I will have one list of values (the ones I put in my BST) and then a list of parameters (min,max,value) that I have to apply to the list of values.

iamdro
  • 41
  • 4

1 Answers1

1

My suggestion would be to follow an approach similar to this answer to another question :

https://stackoverflow.com/a/9320467/1015955

Although, one problem with this would be that you are not using the fact that all the elements are already inserted into a tree.

Or maybe, instead of a binary tree, you could construct a tree that models the recursion tree followed by the above solution ? Just my 2 cents :)

Community
  • 1
  • 1
arya
  • 565
  • 1
  • 6
  • 17