# Binary Search Trees Predesessor & Successor Problems

• 12-08-2005
TheSpoiledMilk
Binary Search Trees Predesessor & Successor Problems
I am coding an implmentation of a standard BST. This is my first implementation I am having problems with the predesessor and successor parts. Maybe someone could lend me some insight.

I have all the find post, in, pre -order traversals i need the succ & pred & delete. I need the succ for the delete and i'm burned put on this program. I need help. :confused:
Here is what i am trying to accomplish.
pred, moves the pointer to the predecessor of the current node, prints the value that proceeds the string or the line "No Previous"

succ, moves the pointer to the successor of the current node, prints the value that follows the string or the line "No Next"

Code:

```//MY GLOBAL STRUCTS FOR THE NODES struct Wrd {       int wordcounter;                                        // counter       string theword;                                        // the actual word }; struct TreeNode {       Wrd item;                                        // the data struct       TreeNode *parent;                                // pointer to the parent       TreeNode *left;                                      // pointer to left subtree       TreeNode *right;                                    // pointer to right subtree }; TreeNode *root = NULL;                                        // root of the tree & init to NULL TreeNode* succ(TreeNode *T){         TreeNode *x, *y;         if (T == NULL){             return T;         }         if (T->right != NULL){             return min(T->right);         }         y = T->parent;         while (y != NULL && x == y->right){                 x = y;                 y = y->parent;         } return y; } //THE CALL  succ(root);```
• 12-08-2005
IfYouSaySo
Successor: Once to the right, and then as far to the left as you can go without hitting null. Pseudocode:

Code:

``` Node* find_successor(Node* root) {     if (!root) return NULL;     root = root->right;     if (!root) return NULL;       while (root->left) {         root = root->left;     }     return root; }```
Predecessor: root->left if not null, otherwise parent of root.
• 12-09-2005
Prelude
>Successor: Once to the right, and then as far to the left as you can go without hitting null.
What's the successor of 4 in the following tree using that definition? If you're only finding the successor in a downward path (such as insertion), then yes, that's correct. But if you want a general successor function you also have to consider upward movement too.
Code:

```        5       /  \     2      9   /  \ 1      4```
Here's a function that finds the successor using parent pointers. A predecessor function just changes right to left and left to right:
Code:

```iNode *succ ( Node *node ) {   if ( node->right != NULL ) {     /* Go down */     node = node->right;     while ( node->left != NULL )       node = node->left;   }   else {     /* Go up */     for ( ; ; ) {       if ( node->parent == NULL || node == node->parent->left ) {         node = node->parent;         break;       }       node = node->parent;     }   }   return node; }```
>Predecessor: root->left if not null, otherwise parent of root.
The predecessor is the exact mirror of the successor in a basic tree, so your description is missing a few steps.
• 12-09-2005
TheSpoiledMilk
Great Thanks!! I got both of those working perfectly.
I have few more questions though involving pointers. I'm pulling my hair out! :mad: :mad:

I need to accomplish the following
> first, moves the pointer to the minimum value in the tree or NULL.
> last, moves the pointer to the maximum value in the tree or NULL.
> root, moves the pointer to point to the root of the tree
> left, moves the pointer to point to the left child of the current node or to NULL.
> right, moves the pointer to point to the right child of the current node or to NULL.

I am confused by how i determine the current node
most of my functions follow the following format for example my function that shows the max of the tree.
Code:

```TreeNode* max(TreeNode *T){//WORKS!!           Wrd e;           if (T == NULL){               cout << "Tree Empty" << endl;               return T;           }           while (T->right != NULL){                 T = T->right;           }           e.theword = T->item.theword;           e.wordcounter = T->item.wordcounter;           cout << e.theword << ":" << e.wordcounter << endl; return T; }```
which is called from my main like so
Code:

`                max(root);`
if my main passes nothing how do i track the current node?
do i need another pointer trailing it like a linked list.
dosen't that break the entire point of trees? :confused:

Can someone explain how i find the current node and manipulate it? Any help would be greatly appreciated!!
• 12-10-2005
Prelude
>I am confused by how i determine the current node
The current node is the one you pass to the function:
Code:

```TreeNode *left ( TreeNode *curr ) {   return curr->left; }```
• 12-11-2005
TheSpoiledMilk
I passed in the root. So am i changing the root? Do i need to keep track of the root?
• 12-11-2005
Prelude
>So am i changing the root?
Only if you assign the return value to your root pointer:
Code:

```root = max ( root ); // Changes root p = max ( root ); // Doesn't change root```