Binary Search Trees Predesessor & Successor Problems

**TheSpoiledMilk** · 12-08-2005

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.

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

**IfYouSaySo** · 12-08-2005

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.

**Prelude** · 12-09-2005

>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:

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.

**TheSpoiledMilk** · 12-09-2005

Great Thanks!! I got both of those working perfectly.
I have few more questions though involving pointers. I'm pulling my hair out!

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?

Can someone explain how i find the current node and manipulate it? Any help would be greatly appreciated!!

**Prelude** · 12-10-2005

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

**TheSpoiledMilk** · 12-11-2005

I passed in the root. So am i changing the root? Do i need to keep track of the root?

**Prelude** · 12-11-2005

>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

Thread: Binary Search Trees Predesessor & Successor Problems

Thread Tools

Search Thread

Display

Binary Search Trees Predesessor & Successor Problems

Similar Threads

Performance issue!

Binary Trees

binary search tree

Ornery binary search algorithm

Newbie questions regarding binary search trees