Click here to Skip to main content
15,352,679 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
#include <iostream>
using namespace std;

// Binary Tree Node class
class Node
{  
    public:
    int data;
    Node *left;
    Node *right;
    Node(int x){
        data = x;
        left = NULL;
        right = NULL;
       
    }
};

 
// Insert a value in our BST
Node* insert(Node* root, int value)
{
    if (root == NULL) {
        return new Node(value);
    }

 
// if root node is greater than value, insert value in left subtree
if (value < root->data) {
    root->left = insert(root->left, value);
}

   
// if root is lesser than value, insert value in right subtree
   else {
       root->right = insert(root->right, value);
   }
   
   return root;
}
 

// Function to find maximum node in a BST
Node* maximumNode(Node* root)

{
    while (root->right) {
        root = root->right;
    }

   return root;
}

 
// Pred node is passed by reference meaning it is making changes in the original node
void findPredecessor(Node* root, Node*&pred, int key)
{
    // base case
   if (root == NULL)
   {
       pred = NULL;
       return;
   }
   // if the root is our key node then the predecessor will be the largest node in its left subtree
   if (root->data == key)
   {
       if (root->left != NULL) {
           pred = maximumNode(root->left);
       }
   }

  // if our key value is less than the root node value then we'll search in left subtree for key node
  else if (key < root->data) {
    findPredecessor(root->left, pred, key);
     
  }
   
   // if our key value is more than the root node value then we'll search in right subtree for key node
   else if (key > root->data) {
       // update predecessor to the current node before recursing in the right subtree
       pred = root;
       findPredecessor(root->right, pred, key);
   }
   return;
}

 
int main()
{
    Node* root = NULL;
    int n=0;

   // Taking BST as input
   while(n!=-1) {
       cin>>n;
       root = insert(root, n);
   }

   // Here we'll take input x and then find it's predecessor
   int x;
   cin>>x;
   Node* pred = NULL;
   
   findPredecessor(root, pred, x);

   // -1 will always be the first node in Inorder traversal because we are taking input BST till -1
   // that means the node with predecessor -1 is the first node in Inorder traversal
   if(pred->data != -1) cout << "The predecessor of node " << x << " is " << pred->data;
   else cout << "The predecessor of node doesn't exist";
   
   return 0;
}
return 0;
}


What I have tried:

I've tried all the possible solutions but still cannot be able to solve it. I need immediate help
Posted
Updated 20-May-22 9:20am
Comments
Greg Utas 20-May-22 15:05pm
   
It's unlikely you'll get any help unless you provide more details as to what error you're getting. A compile error? A link error? A run-time error? Or it just doesn't do what you want? At least you have comments that suggest you're working on a binary search tree, but that's all we know.
wendy sakr 20-May-22 15:10pm
   
error : expected declaration before ‘}’ token
Patrice T 20-May-22 15:19pm
   
And you think you can us the error, or it is secret ?
wendy sakr 20-May-22 15:23pm
   
I think i did lol

Try removing the last two lines.
return 0;
}


You should really try and stick with one brace placing method, it makes things more readable, for example.
if (){
// do something
}

or 

if ()
{
//do something
}
The are many ways of doing this, but the key is consistency.
   
v2
Comments
wendy sakr 20-May-22 15:22pm
   
I have tried. It cannot be run
jeron1 20-May-22 15:42pm
   
Care to elaborate?
merano99 20-May-22 17:58pm
   
It is the right solution to remove the last lines.
Compiling successfully does not mean your code is right! :laugh:
Think of the development process as writing an email: compiling successfully means that you wrote the email in the right language - English, rather than German for example - not that the email contained the message you wanted to send.

So now you enter the second stage of development (in reality it's the fourth or fifth, but you'll come to the earlier stages later): Testing and Debugging.

Start by looking at what it does do, and how that differs from what you wanted. This is important, because it give you information as to why it's doing it. For example, if a program is intended to let the user enter a number and it doubles it and prints the answer, then if the input / output was like this:
Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16
Then it's fairly obvious that the problem is with the bit which doubles it - it's not adding itself to itself, or multiplying it by 2, it's multiplying it by itself and returning the square of the input.
So with that, you can look at the code and it's obvious that it's somewhere here:
C
int Double(int value)
   {
   return value * value;
   }

Once you have an idea what might be going wrong, start using the debugger to find out why. Put a breakpoint on the first line of the method, and run your app. When it reaches the breakpoint, the debugger will stop, and hand control over to you. You can now run your code line-by-line (called "single stepping") and look at (or even change) variable contents as necessary (heck, you can even change the code and try again if you need to).
Think about what each line in the code should do before you execute it, and compare that to what it actually did when you use the "Step over" button to execute each line in turn. Did it do what you expect? If so, move on to the next line.
If not, why not? How does it differ?
Hopefully, that should help you locate which part of that code has a problem, and what the problem is.
This is a skill, and it's one which is well worth developing as it helps you in the real world as well as in development. And like all skills, it only improves by use!
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900