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);
}
}

 

[quicknote]

I would suggest implementing n1 and n2 by using the properties of a binary search tree. Since the tree is already sorted in alphabetical order, we can use the fact that the left child of a node is always smaller and the right child is always larger.

To find n1, we can start at the root node and traverse the tree to the left until we reach a node whose key is smaller than x. This node will be the nearest node to x in alphabetical order. If we reach a leaf node without finding n1, then n1 does not exist in the tree.

To find n2, we can start at the root node and traverse the tree to the right until we reach a node whose key is larger than x. This node will be the nearest node to x in alphabetical order. If we reach a leaf node without finding n2, then n2 does not exist in the tree.

These steps can be implemented in the code by adding additional conditions to the existing code. For example, to find n1, we can add a condition in the else if statement for when x < treeRoot->name. This condition would check if treeRoot->left is NULL, and if it is, then we have found n1. Similarly, for finding n2, we can add a condition in the else if statement for when x > treeRoot->name, checking if treeRoot->right is NULL.

Additionally, we can also keep track of the previous node while traversing the tree, and if we reach a leaf node without finding n1 or n2, we can use the previous node as n1 or n2 respectively. This would cover the case when x is not present in the tree and n1 or n2 is the last node in the tree.

Overall, implementing n1 and n2 would involve using the existing code and adding additional conditions to handle the cases when x is not found in the tree.