CODEWITHSUNDEEP
calgorithmbinary-search-tree
PlayHardGoPro
PlayHardGoPro

Reputation: 2933

Find the first key bigger than X on Binary Search Tree

The successor of an element in a BST is the element's successor in the sorted order determined by the inorder traversal. Finding the successor when each node has a pointer to its parent node is presented in CLRS's algorithm textbook (Introduction to Algorithms by MIT press).

Is there a way to find the first value that is bigger than X without parent in the struct? Like: 

typedef struct tree tree;
struct tree{
   int value;
   tree *left;
   tree *right;
};

//Function:  

tree *find_first_bigger(tree *t, int x){}

I tried working with: 

tree *find_first_bigger(tree *t, int x){
   if(t == NULL)
      return NULL;

   if((*t)->value > x)
      find_first_bigger((*t)->left, x);

   else if((*t)->value < x)
      find_first_bigger((*t)->right), x);
   else if((*t)->value == x){
      if((*t)->right != NULL) 
         return tree_first_bigger((*t)->right);
      else
         return tree;
   }
}

With this example(it's using letter but there its not a problem), if I try to search the first bigger than N(It should return me O) but it returns me N.

Search Binary Tree

Upvotes: 2

Views: 5926

Answers (4)

Deepak Sharma
Deepak Sharma

Reputation: 652

I haven't tested this, but I think it should work. Let me know if it is wrong. //c++ 11

 #include<iostream>
 using namespace std;
 struct BSTNode{
     int val;
     BSTNode* left;
     BSTNode* right;
 };


 int FindJustLarger(BSTNode*& node, int token, int sofarlarge){
    // for invalid inputs it will return intial value of sofarlarge
    // By invalid input I mean token > largest value in BST
    if(node == nullptr)
        return sofarlarge;

    else if(node->val > token){
        sofarlarge = node->val;
        return FindJustLarger(node->left, token, sofarlarge);}

    else
        return FindJustLarger(node->right, token, sofarlarge);}

int main(){
    BSTNode* head = new BSTNode{5, nullptr, nullptr};
    FindJustLarger(head, 5, NULL);
    delete head;
    return 0;}

Upvotes: 0

Sumeet
Sumeet

Reputation: 8292

You have done 90% of the job.Allow me to do the remaining 10%.

Since t is a pointer to structure you should use t->left instead of (*t)->left and same applies while accessing right and value fields of the struct.

Now, Just modify your function as:

Add this as first line of your function

static tree* PTR=NULL;

Modify the second if condition as:

if(t->value > x)
 {
     PTR=t;
     find_first_bigger(t->left, x);
 }

Modify the second else if condition as:

else if(t->value == x)
{
  if(t->right != NULL)
     {
         t=t->right;
         while(t->left!=NULL)
            t=t->left;
         return t;
     }
  else return PTR;
}

Hence the correct function is

tree *find_first_bigger(tree *t, int x)
{
   static tree* PTR=NULL;
   if(t == NULL)
      return NULL;
   if(t->value > x)
     {
         PTR=t;
         find_first_bigger(t->left, x);
     }
   else if(t->value < x)
       find_first_bigger(t->right, x);
   else if(t->value == x)
    {
      if(t->right != NULL)
         {
             t=t->right;
             while(t->left!=NULL)
                t=t->left;
             return t;
         }
      else return PTR;
   }
}

In the main function if pointer returned is NULL, this means that :the key itself is the largest key. Feel free for any queries.

Upvotes: 2

KalyanS
KalyanS

Reputation: 527

In your question, you seemed to indicate that you want to find out InOrderSuccessor() of the the given value 'x'.

If 'x' does not necessarily exist in the tree, we need to change the algorithm. Given the example you provided and the problem statement, here is code for finding the next element in a BST.

The key cases are :

  • No greater element exists, because 'x' is the biggest.
  • 'x' has a right child ?
  • YES: get left-most child of x's right sub-tree.
  • NO : return parent.

Key observation is that we don't update the parent pointer, whenever we go right in the tree.

  tree *ptr = root;
  tree *prnt = NULL;
  while (ptr != NULL) {
      if (x == ptr->key) {
          if (ptr->right != NULL) {
              return GetLeftMostChild(ptr->right);
          } else {
              return prnt;
          }
      } else if (x > ptr->key) {
          ptr = ptr->right;
      } else {
          prnt = ptr;
          ptr = ptr->left;
      }
  }

Here is the definition for leftMostChild()

tree *GetLeftMostChild(tree *n) {
    tree *ptr = n;
    while (ptr->left != NULL) {
        ptr = ptr->left;
    }
    return ptr;
}

Upvotes: -1

Juan Lopes
Juan Lopes

Reputation: 10575

Some changes you can do in your code:

  • You have to return the values from the recursive calls

  • If the value is not found, return NULL. This means returning NULL if t->right == NULL on the last if.

  • When going to the left, if the value is not found there, the answer must be the node itself. In the case of N, it is the last node where we turn left: O. If it were P, the answer would be T itself.

After all those changes, the code should look like this:

tree *find_first_bigger(tree *t, int x){
   if(t == NULL)
      return NULL;

   if(t->value > x) {
      tree *answer = find_first_bigger(t->left, x);
      if (answer != NULL) 
          return answer;
      return t;
   } else if(t->value < x) {
      return find_first_bigger(t->right, x);
   } else if(t->value == x) {
      if (t->right != NULL)
          return tree_first_bigger(t->right);
      return NULL;
   }
}

You can find the entire code I used to test in this gist.

Upvotes: -1

Related Questions