CODEWITHSUNDEEP
c++binary-tree
Vicky
Vicky

Reputation: 13

Simplest binary tree insertion is not working

#include<iostream>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
    node(int value = 0);
};
node::node(int value){
    data = value;
    left = NULL;
    right = NULL;
}


class LinkedList{
    public:
        node *root;
        LinkedList();
        bool isEmpty();
        void insertInto(int value, node *key);
};

LinkedList::LinkedList(){
    root = NULL;
}

bool LinkedList::isEmpty(){
    if(root == NULL) return true;
} 

void LinkedList::insertInto(int value, node* root){
    if (root == NULL)
    {
        node *n = new node(value);
        root = n;
    }
    else if(value <= root->data){
        insertInto(value, root->left);
    }
    else if(value > root->data){
        insertInto(value,root->right);
    }
}


int main() {
    cout<<"I am gonna write the insertion of a binary tree"<<"\n";
    LinkedList sample;
    if(sample.isEmpty()) cout<<"THe tree is empty"<<endl; else cout<<"The tree is NOT empty"<<endl;
    sample.insertInto(5,sample.root);

    if(sample.isEmpty()) cout<<"THe tree is empty"<<endl; else cout<<"The tree is NOT empty"<<endl;



    return 1;
}

I have been working on this for quite some time, I dont seem to understand why the result is showing that the tree is empty even after adding the value 5. ALso please give tips on how I can improve. Thanks

Upvotes: 0

Views: 110

Answers (1)

bobroxsox
bobroxsox

Reputation: 992

Ignoring the comments that I could make about the style/structure of the code you've posted:

    void LinkedList::insertInto(int value, node* root){
        if (root == NULL)
        {
            node *n = new node(value);
            root = n;
        }

You're not passing the node* root variable by reference here. Instead, you're changing a copy of the node* root to point to the new node object you constructed. If you want this code to actually change the value of the sample.root variable that you passed in from the main, you must pass root by reference. 

    void LinkedList::insertInto(int value, node* &root){

Since LinkedList::insertInto is a member function anyway, why pass in root at all? You have access to the member variable root, just use that instead. If you still want to be able to use it recursively, you could make a public function with just the value, and have that call a private version that also takes in a node* is a parameter.

Here are some coding style suggestions, since you asked for them:

Best coding practice dictates that you make member variables of your class private, and use public member functions to manipulate your class instead. This is for a variety of different reasons. One explanation is here:
https://softwareengineering.stackexchange.com/questions/143736/why-do-we-need-private-variables

So your class (and let's call it BinaryTree instead), would look something like this:

class BinaryTree{
    public:
        /*  functions  */
    private:
        node *root;
};

So instead of making the user of the class provide the root of the BinaryTree (which doesn't make sense since we know it anyway), we just ask them for the value to insert, and provide the root ourselves.

class BinaryTree{
    public:
        /*  other functions  */
        void insertInto(int value);
    private:
        void insertInto(int value, node* &n);
        node *root;
};

// Public version of the insertInto function
void insertInto(int value) {
    insertInto(value, root);
}

// Private helper function for insertInto
void insertInto(int value, node* &n) {
    if (n == NULL)
    {
        n = new node(value);
    }
    else if(value <= root->data){
        insertInto(value, root->left);
    }
    else if(value > root->data){
        insertInto(value,root->right);
    }
}

int main() {
    BinaryTree sample;
    sample.insertInto(5);
}

Upvotes: 2

Related Questions