Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binary Search Tree C++

  1. Apr 11, 2009 #1
    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 )
    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);
    n1 = NULL;
    n2 = NULL;
    return treeRoot;

  2. jcsd
  3. Apr 16, 2009 #2
    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);
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook