How to find a certain element of BST, given key?

Question

So I'm trying to implement a TREE_SUCCESSOR(X) function for BST where X is the key of the node that I'm trying to find the successor of. So far I have this:

int BinarySearchTree::TREE_SUCCESSOR(node* x)
{
//i dont need a new node, I just need a pointer/reference to x. 
node* y = NULL;
//node* parent = NULL;
if (x->right != NULL)
{
    return FIND_MIN(x->right);
}
else
{
    y = x->parent; 
    while (y != NULL && x == y->right)
    {
        x = y;
        y = y->parent;
    }
    return y->key; 
}
}

My problem is in the main function:

int main()
{
BinarySearchTree bst;
int num = 0; 
cout << "Enter number you want to find the successor of: " <<endl; 
cin >> num; 

if(BST.root->key == num)             //if i'm trying to find the successor of the root
   { TREE_SUCCESSOR(BST.root); } 
else
{ 
    while(BST.root->key != num)      //if the user input does not equal the root key value 
    { 
        ???? 
    }
}

I want to find out how to traverse the BST to the node of the BST till the key = num. For example, if the tree had nodes 3,4,5 then TREE_SUCCESSOR(4), should return 5. How would I do this??

EDIT

So I decided used a TREE_SEARCH(key) that would find the node with a certain key and return it... and then pass that node into TREE_SUCCESSOR(X).

AFAIK it is just a convention: http://stackoverflow.com/questions/3799478/c-ifndef-for-include-files-why-is-all-caps-used-for-the-header-file — NathanOliver, Jul 01 '15 at 18:53
It is convention and everyone will hate you if you don't follow it. All uppercase is used for named constants. This is true across pretty much every programming language I've used. — Rob K, Jul 01 '15 at 20:02
@RobK Lol I will change.. in fact my professor had it that way, so when I created a different method, I just followed the same convention. — ocean800, Jul 01 '15 at 20:59

score 1 · Accepted Answer · answered Jul 01 '15 at 18:48

1

Do an in-order traversal.

After finding the element continue the traversal, the next element is the one you need.

You don't need any special case regarding if you're looking for the successor of the root, but you need to treat the case where the element is the last one in the traversal, i.e. the largest one one.

answered Jul 01 '15 at 18:48

Radu Diță

13,476
2
30
34

well I can't use an inorder traversal to find the successor, I'm required to use a successor method. – ocean800 Jul 01 '15 at 18:53
I was under the impression you had to write a successor method. The successor method is actually what I described above. – Radu Diță Jul 01 '15 at 18:56
Maybe I misunderstood... I was saying that I have to use the successor method in the way that I wrote it above, and that I cannot use in-order traversal to find the successor. – ocean800 Jul 01 '15 at 19:04

score 1 · Answer 2 · answered Jul 01 '15 at 19:02

My first approach would be to search for examples on the internet "binary search tree successor".

But if I have a big enough ego, I may want to develop my own algorithm. I would draw a binary search tree. Next I would pick a node an figure out the steps to get to the successor. After I have the steps, I would go through the steps using different nodes on the tree and adjust the algorithm (steps) as necessary.

After I had the algorithm, I would code it up.

But you're not me, so you would want to search the internet for "c++ binary search tree successor function".

How to find a certain element of BST, given key?

2 Answers2