CODEWITHSUNDEEP
c++c++11binary-search-tree
Jumper
Jumper

Reputation: 215

Traversing a binary search tree

I've implmented a basic binary search tree. Here's my node

 #ifndef NODE_H
    #define NODE_H

    template<typename T> class node{

        template<typename E> friend class bst;

        public:
            node():data(0), left(NULL), right(NULL){}
            node(T data):data(data),left(NULL), right(NULL){}   

        private:
            T data;
            node<T>* left;
            node<T>* right;
    };

#endif

And here's my bst.

#ifndef BST_H
#define BST_H

template<typename T> class bst{
    public:
        bst():root(NULL), nodes(0){}
        bst(node<T>* root):root(root), nodes(0){}

        void insert(node<T>* root, const T& data){

            if(root == NULL){
                node<T>* root = new node<T>();
                root->data = data;
                nodes++;
                return;
            }else if(data <= root->data) {
                insert(root->left, data);

            }else if(data >= root->data){
                insert(root->right, data);

            }
        }

        void preorder(node<T>* root){
            if(root == NULL) return;
            std::cout<< root->data<<'\n';

            preorder(root->left);
            preorder(root->right);
        }
    private:
        node<T>* root;
        int nodes;
};
#endif

Here's the calling function

int main(){

    node<int>* root = new node<int>(17);
    bst<int>* t = new bst<int>(root);


    t->insert(root,21);
    t->insert(root,12);
    t->insert(root, 9);

    t->preorder(root);

    delete t;
}

The output is simply 17, which is the root. I feel somehow my insert method hasn't worked right, since the preorder is a pretty standard implementation. Can somebody help me as to what is going wrong here.

Upvotes: 1

Views: 453

Answers (3)

marom
marom

Reputation: 5230

Inside insert do not create a local variable, just use the one passe. So instead of

node<T>* root = new node<T>();

do just

root = new node<T>();

And pass root by reference. I would do it with a typedef

typedef node<T>* nodePtr;
void insert(nodePtr &root, const T& data){

but you can do it also without

Upvotes: 2

lrleon
lrleon

Reputation: 2648

I see two problems.

The first is that you are declaring root as a local variable inside insert() method. This name overlaps to data member root.

The second is that, as you have designed it, the root is not updated.

This code should work:

void insert(node<T>*& root, // <-- root as reference for updating
            const T& data){

        if(root == NULL){
            root = new node<T>(); // <-- here you update root
            root->data = data;
            nodes++;
            return;
        }else if(data <= root->data) {
            insert(root->left, data);

        }else if(data >= root->data){
            insert(root->right, data);

        }
    }

Of course, you could refactor and thus to get a more concise and elegant implementation. But this should produce the result that you expect

Upvotes: 1

Aron Monszpart
Aron Monszpart

Reputation: 108

You have to pass the root by refrence, and do not create a local variable shadowing it:

// ...
void insert(node<T>*& root, const T& data){ // passed by reference

            if(root == NULL){
                root = new node<T>();       // reference overwritten
//...

This gives me 

17
12
9
21

as output, as expected of preorder I guess.

Upvotes: 1

Related Questions