Binary Search tree

I am unable to implement the insert function properly,every time i run the program i just get the first value and name,i am not getting other Id's and name.Please help!Thanks

Code:

---

"(Header File)"

#include <iostream>
#include <string>
using namespace std;


class node
{
  public:
  int ID;
  node (string StudentName, int IDNumber) {
  name = StudentName;
  ID = IDNumber; // key value
  left = NULL;
  right = NULL;
  parent = NULL;
}
}; // end class node

class bst {
                class node *root; // root of the tree

              // print in ascending order of IDs

void printInOrder(class node *n)
 {
  if (n == NULL){
          //nothing to print
            return;}
           
  // recursively print left sub-tree

              printInOrder(n->left);

              // print this node;

              cout << "<" << n->ID << ", " << n->name << ">" << endl;

              // recursively print right subtree

              printInOrder(n->right);
}

public:
        bst() {
                  root = NULL;}

void print() {
                  printInOrder(root);
}

bool insert(string StudentName, int IDNumber);

      // returns true if successfully inserted
      // otherwise returns false (if matching ID exists in BST)

};



"(Main file)"


#include "bst.h"

int main() {
             
class bst *tree = new bst();

while (1) {
  int choice;

  // 1 to insert a record, 2 to remove a record, 3 to print records in ascending order of IDs, 0 to exit

  int StudentID;

  string StudentName;

  cout << endl << "Enter choice (1 to insert a record, 2 to remove a record, 3 to print records, 0 to exit): ";

  cin >> choice;

if (choice == 0) {
break;
}

else if (choice == 1) {
        cout << endl << "Enter new student ID: ";
        cin >> StudentID
        cout<< "Enter new student name: ";
        cin >> StudentName;
    if (tree->insert(StudentName, StudentID))
    cout << "New student record inserted in BST" << endl;
else
cout << "Failed to add new student record in BST - matching ID exists" << endl;
}
if (choice == 3) {
cout << "Printing student records in ascending order of IDs" << endl;
tree->print();
}
}
system("pause");
}

"BST File(Implementation file)"

#include "bst.h"

using namespace std;

bool bst::insert(string StudentName, int IDNumber) {


        class node * n= new node(StudentName,IDNumber);
        class node * parent = NULL;


        if(root == NULL)
                root = n;
        else
        {
               
               

                      // Need help here




//implement the function here
// you will need to create a new node with given student name and ID
// then traverse the tree (starting at the root) to find the right
// place to insert the node

// if a node with matching ID is found, return false to indicate failure

// if given ID is less than the ID of the node you are inspecting, move
// to the left subtree. If the given ID is greater, move to the right subtree

// end insert

---

Quote:

---

Originally Posted by talhakhan797

every time i run the program

---

Programming is much more than just writing code and running it. What have you done to debug your program? When you debug your program, what line, function, variable, etc. goes against what you expected?

Regards,

Paul McKenzie

Being able to debug programs is an essential skill of becoming a programmer. The basic steps for any program are
design, code, test/debug.

In this case, you haven't even attempted to code the missing functions, so no wonder the program doesn't work properly! As this is an assignment, we won't provide the code for you as that would be cheating. See http://forums.codeguru.com/showthrea...ork-assignment

Your first step is to understand the provided code and then to design the required functions, then code them and then test/debug. If you are having trouble understanding binary search trees, an internet search provides plenty of information eg
https://www.google.co.uk/search?q=bi...LciVhQexuoCQBQ
http://en.wikipedia.org/wiki/Binary_search_tree

The only problem i am having now is that id's are not been printed except root node but when i debug the program and print the current and root note by inserting cout,it shows everything correct(correct root node and current node).Please point out where i am doing the mistake!thanks

Code:

---

bool bst::insert(string StudentName, int IDNumber)
{
       
       
        class node * n= new node(StudentName,IDNumber);
        class node * current, *temp = NULL;
        current = root;

        if(root == NULL)
        {
                root = n;
                return 1;
        }
        else if(root->ID == n->ID)
                return 0;
        else if(root->ID > n->ID) //for Left Subtree
        {               
                current = current->left;
                if(current == NULL)
                {
                                current = n;
                                current->parent = root;
                               

                                return 1;
                }
                else
                {
                        while( !(current->left == NULL && current->right == NULL) )
                        {               
                                if(current->ID == n->ID)
                                        return 0;
                                else if(current->ID > n->ID)
                                        current = current->right ;
                                else
                                {
                                        current = current->left;
                                }

                        }
                        if(current->ID > n->ID)
                        {       
                                current->left = n;
                                n->parent = current;
                               

                                return 1;
                        }
                        else
                        {
                                current->right = n;
                                n->parent = current;
                               

                                return 1;
                        }
       
                } 
        }
        else
        {               
                current = current->right;
                if(current == NULL)
                {
                                current = n;
                                current->parent = root;
                                return 1;
                }
                else
                {
                        while( !(current->left == NULL && current->right == NULL) )
                        {               
                                if(current->ID == n->ID)
                                        return 0;
                                else if(current->ID > n->ID)
                                        current = current->right ;
                                else
                                {
                                        current = current->left;
                                }

                        }
                        if(current->ID > n->ID)
                        {       
                                current->left = n;
                                n->parent = current;
                                return 1;
                        }
                        else
                        {
                                current->right = n;
                                n->parent = current;
                                return 1;
                        }
       
                } 
        }

---

}

Quote:

---

Originally Posted by talhakhan797

but when i debug the program and print the current and root note by inserting cout,

---

Run your code using the debugger, not by using cout. Step through the code in the debugger

Quote:

---

it shows everything correct

---

Which proves that using "cout" is not enough. If you say it is "correct", then there is nothing wrong. If you now say there is something wrong, then it isn't "correct".

Quote:

---

Please point out where i am doing the mistake!

---

Did you write the code? If so, then you're supposed to know exactly what every line, function, etc. is supposed to do. If the program doesn't do what you planned it to do, then you step through the program using the debugger to see where it goes against your plan. You don't write code randomly and not know what every single function, loop, line, etc. is supposed to do.

Second, when dealing with trees, you should have written down on paper using boxes, arrows, etc. how linked lists are supposed to work in terms of insertion, deletion, etc. before writing a single line of code. If you did that first, then there should be no problem with writing the code that mimics the pictures drawn.

Third, the code you posted has no "cout" statements. It also doesn't show us how you're calling this code, and you don't have a main() function that is testing this code. Just showing us a function doesn't tell us how you're using the function.

Regards,

Paul McKenzie