### Thread: Need help with BST and search function

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
3

#### Need help with BST and search function

Hi guys.

i need to write a recursive function that takes three parameters: tree's root, key, and a pointer to a function that measure the distance between two given keys, and returns the node that holds the closest key to the given key.
according to my assignment instructions, i'm not allowed to change the function prototype, and i have to deal with what i've got.

so, here's the prototype:
Code:
`node_t FindClosestNode(node_t root, key_t key, dist_func_t distanceFunc );`
node_t and key_t are pointers to void:
Code:
```typedef void* key_t;
typedef void* node_t;```
dist_func_t is a pointer:
Code:
`typedef int (*dist_func_t)(key_t key1, key_t key2);`
distanceFunc returns the distance between two keys (either strings or integers).

as you probably already noticed, it's impossible to compare between the given key and a current.node->key.
i can only measure distance between them. :|
which makes this assignment a big pain. so i can really use some help here.

after countless efforts and attempts, i managed to write something the works (kind of):

Code:
```node_t FindClosestNode(node_t root, key_t key, dist_func_t distance)
{
struct node* iterator=root; //casting

if (distance(iterator->key, key)>distance(iterator->left->key, key)) //if the given key is closer to the left child
return FindClosestNode(iterator->left, key, distance);
else if (distance(iterator->key, key)>distance(iterator->right->key, key)) //if the given key is closer to the right child
return FindClosestNode(iterator->right, key, distance);
else  //else - the given key is closer to current node
return iterator;
}```
my problem is this:
i couldn't think of any exit condition, and - most importantly - i couldn't figure out how to handle the cases where a node has no left/right child.
and that obviously causing a segmentation fault, since "distance" has to measure the distance between non valid keys.

any help would greatly appreciated.
also, i'd love to hear about other ideas on how to implement this function.
thanks in advanced!
Last edited by so.very.tired; February 21st, 2013 at 09:05 AM.
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
3
Yay!
i did it. :D

Code:
```node_t FindClosestNode(node_t root, key_t key, dist_func_t distance)
{
struct node* iterator=root; //casting

if (iterator->left)
if (distance(iterator->key, key)>distance(iterator->left->key, key))
return FindClosestNode(iterator->left, key, distance);
if (iterator->right)
if (distance(iterator->key, key)>distance(iterator->right->key, key))
return FindClosestNode(iterator->right, key, distance);
return iterator;
}```
and i know it's kind of an ugly code, but it works...
Last edited by so.very.tired; February 21st, 2013 at 10:12 AM.
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
3
nope.
it has a major bug in it. :(

i can really use guidance:
how can i find closest node without the abilty to compare between the keys?
4. Don't you want something like
Code:
```d1 = distance(iterator->key, key);
d2 = iterator->left ? distance(iterator->left->key, key) : INT_MAX;
d3 = iterator->right ? distance(iterator->right->key, key) : INT_MAX;```
if d1 is smallest, then the current node is the answer.
if d2 < d3, then go left, otherwise go right.
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
3
Hi salem.

what does INT_MAX represent?
6. Well in terms of the code posted, it means the furthest possible distance.

If you're after what INT_MAX is in C terms, try google.
7. Consider a tree like
Code:
```    10
/  \
2    12
/ \
1   8```
and searching for 8.
8. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
3
thanks salem.
but as requinix pointed out, this code won't work.

I was thinking maybe to try adopting some ideas from here, but i just can't make that work without comparing two keys...
9. Originally Posted by so.very.tired
Hi salem.

what does INT_MAX represent?
Or you could read the limits.h header file.

HINT: with the finite number of bits in an integer type, there are minimum and maximum limits to the values you can represent with that many bits. There are times in your program when you would want to know what those minimum and maximum values are. Also bear in mind that the size of an int can be different with different compilers, so that information is provided to you through the limits.h header file.
10. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
132
Rep Power
3
OK.

that's the best i could come up with:

Code:
```node_t FindClosestNode(node_t root, key_t key, dist_func_t distance)
{
struct node* iterator=root, leftNode=NULL, rightNode=NULL;
int dCurrent, dLeft, dRight;
dCurrent=distance(iterator->key, key);

if (iterator->left)
{
leftNode=FindClosestNode(iterator->left, key, distance);
dLeft=distance(leftNode->key, key);
}
if (iterator->right)
{
rightNode=FindClosestNode(iterator->right, key, distance);
dRight=distance(rightNode->key, key);
}

if ((!iterator->right)&&(!iterator->left))
return iterator;
if (!iterator->right)
return dLeft<=dCurrent ? leftNode : iterator;
if (!iterator->left)
return dRight<=dCurrent ? rightNode : iterator;
if ((iterator->right)&&(iterator->left))
{
if (dRight<=dCurrent) return rightNode;
else if (dLeft<=dCurrent) return leftNode;
else return iterator;

}```
if anyone have tips/advices/ideas on how to make this code more efficient, i'd love to hear.