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

Question

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

Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine at which point your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Andreas Wenzel, Apr 15 '22 at 10:42
Please [add output as text](https://meta.stackoverflow.com/questions/285551). — codeling, Apr 15 '22 at 10:47

Vlad from Moscow · Answer 1 · 2022-04-15T11:10:16.900

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

I should add that this is for a school assignment. The class Node and Class BST member functions were given to me as a guide. — Jorge Lopez, Apr 15 '22 at 10:59

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

1 Answers1