Find Nearest Record in Binary Search Tree | C++ Implementation

[skyhyyzlz]

Hi everyone, i have a binary search tree proble, please help me..


* Find record with key x in the tree. If not found, return the two nearest records in the tree (in alphabetical order)
* Return values:
* FOUND: Return the address of the node in the tree which contains key x, set n1 = n2 = NULL;
* NOT FOUND: Return NULL, n1, n2 are set to the nearest node to x in the tree, if exist.
* n1 is set to the address of the BSTNode whose key is just smaller than x in alphabetical order, if exists (Otherwise NULL).
* n2 is set to the address of the BSTNode whose key is just larger than x in alphabetical order, if exists (Otherwise NULL).
* NOTE:
* Always return the address of the existing "BSTNode"s. DO NOT allocate new spaces for returned strings.

How can I implement n1 and n2 in the following code for finding the nearest record when the key x is NOT FOUND?


const BSTNode * BST_findNearest( BSTNode * treeRoot, const string & x, BSTNode* &n1, BSTNode* &n2 )
{
if(treeRoot==NULL)
{
return NULL;
}
else if(x < treeRoot->name)
{
return BST_findNearest(treeRoot->left,x,n1,n2);
}
else if(x > treeRoot->name)
{
return BST_findNearest(treeRoot->right,x,n1,n2);
}
else
{
n1 = NULL;
n2 = NULL;
return treeRoot;
}

}

 

[Mizuho]

From your question, I think I'm taking same course with you, in same University.
Just simply set n1 or n2 before returning the next node.

const BSTNode* BST_findNearest( BSTNode* treeRoot, const string &x, BSTNode* &n1, BSTNode* &n2 )
{
if (treeRoot == NULL) return NULL;
if (x == treeRoot->name) {
n1 = n2 = NULL;
return treeRoot;
}
else if (x < treeRoot->name) {
n2 = treeRoot;
return BST_findNearest(treeRoot->left, x, n1, n2);
}
else if (x > treeRoot->name) {
n1 = treeRoot;
return BST_findNearest(treeRoot->right, x, n1, n2);
}
}