Binary Search Tree is printing a random 0 and I can't find where its being created

user_18812055 0
Viewed 49

I am working on a BST and when I print out the elements in any order, I get a random '0' appended to it, but I cannot find where its coming from. I followed the pseudo code thats present in Introduction to algorithms by Cormen and have also looked at Geeks for Geeks but I have no luck getting rid of that 0.

#include <iostream>
using namespace std;
class Node {

public:
    int data;
    Node* LeftChild;
    Node* RightChild;
    Node(int data){
        this->data = data;
        this->LeftChild = NULL;
        this->RightChild = NULL;
    }
    //pointers of the class
};

class BST {
private:
    Node* root;
public:

    BST(){ ///creating an empty tree in Constant Time
        root = new Node(NULL);
    }

    Node* getRoot(){ return this->root; };

    int i =0;

    void printTree(Node *root)
    {
        if (root == NULL)
            return;
        else {
            printTree(root->LeftChild);
            cout << root->data << " ";
            printTree(root->RightChild);
        }
    }

    Node* InsertNode(Node *root,int data)
    {
        Node *z = new Node(data);
        Node *y = new Node(NULL);
        Node *x = this->root;

        //if(x->data < z->data){
          //  x = z;
            //return x;
        //}

        while(x!= NULL){
            y = x;
            if(data < x->data){
                x = x->LeftChild;
            }
            else{
                x = x->RightChild;
            }

        }

        if(y== NULL) y= z;

        else if(data < y->data){
            y->LeftChild = z;
        }
        else{
            y->RightChild =z;
        }

        return y;

/*
        if(this->root->data== NULL){
            this->root =z;
            return root;
        }
        else{
            this->root =y;
        }
*/

        //this->root = z;
        //return root;
    }

    bool FindNode(Node *root,int data);
    int Largest(Node *root){
        return root->data;

    }
};


int main()
{
    BST myBst;
    Node * root = (myBst.getRoot());
    root = myBst.InsertNode(root, 24);
    myBst.InsertNode(root, 60);
    myBst.InsertNode(root, 55);
    myBst.InsertNode(root, 32);
    myBst.printTree(root);
    return 0;
}

Here is the output:

0, 24,32,55,60
binary-search-tree initialization class constructor c++
1 Answers

The constructor does not make a sense

BST(){ ///creating an empty tree in Constant Time
root = new Node(NULL);
}

There is created a dummy node with initialization of the data member data with NULL.

What you need is just to write

BST() : root( nullptr ) { ///creating an empty tree in Constant Time
}

The function InsertNode must have only one parameter instead of two parameters as you wrote

Node* InsertNode(Node *root,int data){

The pointer root is the data member of the class. So there is no need to pass it to the function. Otherwise the function should be declared as a static member function of the class (that nevertheless does not make a great sense).

That is the function should be declared like

void InsertNode( int data ){

Also the function has at least a memory leak

Node* InsertNode(Node *root,int data){
     Node *z = new Node(data);
     Node *y = new Node(NULL);
     Node *x = this->root;

     while(x!= NULL){
         y = x;
         //...

The function can be written for example the following way

void InsertNode( int data )
{
    Node *new_node = Node( data );
    Node **current = &root;

    while ( *current != nullptr )
    {
        if ( data < ( *current )->data )
        {
            current = &( *current )->LeftChild;
        }
        else
        {
            current = &( *current )->RightChild; 
        }
    }

    *current = new_node;
}
user_28772410
Related