BST implementation in c++

Question

I wanted to study c++ so i took up algorithms.I have implemented a Binary search tree with insert,delete,inorder and minimum element functions.I would like to have some feedback and some pointers to do things better.Anything is appreciated.

code:

#include <iostream>
using namespace std;

//This represents my tree node
struct node{
    int value;
    node *left,*right;
};

//minimum value of bst
node* minValue(node* tnode){
    if(tnode->left!=NULL){
        return minValue(tnode->left);
    }
    else{
        return tnode;
    }

}

//Inorder traversal
void inorder(node *tnode){
    if(tnode->left!=NULL){
        inorder(tnode->left);
    }
    cout<<tnode->value;
    if(tnode->right!=NULL){
        inorder(tnode->right);
    }

}

//insert function
node* insert(int val,node *tnode){
    node *temp=tnode;
    if(temp==NULL){
        temp= new node;
        temp->value=val;
        temp->left=NULL;
        temp->right=NULL;
    }
    else if(val<temp->value){
        temp->left=insert(val,temp->left);
    }
    else if(val>temp->value){
        temp->right=insert(val,temp->right);
    }

    return temp;
}

//delete function
node* deleteNode(node* tnode,int val){

    if(tnode==NULL) 
        return tnode;
    if(tnode->value>val){
        tnode->left=deleteNode(tnode->left,val);
    }
    else if(tnode->value<val){
        tnode->right=deleteNode(tnode->right,val);
    }
    else{
        if(tnode->left==NULL){
            node* temp=tnode->right;
            delete tnode;
            return temp;
        }
        else if(tnode->right==NULL){
            node* temp=tnode->left;
            delete tnode;
            return temp;
        }
        node* temp=minValue(tnode->right);
        tnode->value=temp->value;       
        tnode->right=deleteNode(tnode->right,temp->value);
    }
    return tnode;

}
int main(){
cout<<"Binary Tree";
node *ROOT=NULL;
ROOT=insert(3,NULL);
insert(2,ROOT);
insert(5,ROOT);
insert(4,ROOT);
insert(1,ROOT);
insert(7,ROOT);
insert(8,ROOT);
deleteNode(ROOT,3);
inorder(ROOT);
return 0;
}

The code is broken, in at least 2 different cases deleteNode() does not return a pointer to node. This can be fixed by adding one line. Other than the use of std::cin and std::cout this is actually C code rather than C++. — pacmaninbw
– pacmaninbw ♦, Commented May 17, 2017 at 18:52
Should i use a class here? Is it the reason its not c++ and rather looks like c? Sorry but i am very new to c++. — Anantha Padmanaban
– Anantha Padmanaban, Commented May 17, 2017 at 18:59
@pacmaninbw std::cout and std::cin is excactly C++?! Can you elaborate your point? — miscco
– miscco, Commented May 17, 2017 at 19:00
Even struct's can have pointers to functions, but I see 2 distinct clases here. Tree is one class with the functions insert, delete and traverse. Node is another class. — pacmaninbw
– pacmaninbw ♦, Commented May 17, 2017 at 19:01
Thank you for the feedback.I'll keep it in mind when i write the next c++ program. — Anantha Padmanaban
– Anantha Padmanaban, Commented May 17, 2017 at 19:04

Community · Accepted Answer · 2020-06-10 13:24:26Z

Design

Lets start by saying this is a C solution to the problem. You need to think more about classes encapsulation and protecting the tree from random coders to make sure your enviranrts remain protected.

Something like:

class BSTTree
{
    struct node { /* As you had */ };

    node*   root;
    public:
        // Constructors/Destructors and assignment here.

        void insert(int value);
        void delete(int value);
        void inorder(std::function<void(int)> action) const;
        int minimum() const;
};

Notice how we hide root to make sure only the methods you write can manipulate the tree. Nobody else can come along and tinker with it. This means if your code is correct then the enviranrts can not be changed.

Also you have not dealt with any of the issues around memory management. So you need to think about this. Who owns each node how are you going to delete them safely. Also look up the rule of three before you write your class (implement that are the rule of zero).

Also you should probably avoid NULL it modern C++ it has been replaced by nullptr. The advantage of nullptr is that it has a well defined type that is not convertible to an integer type.

Code Review

Sure this works:

node* minValue(node* tnode){
    if(tnode->left!=NULL){
        return minValue(tnode->left);
    }
    else{
        return tnode;
    }    
}

Should you return a node? The function says min value. SO why not return the minimum value. Also you don't want to expose the implementation details and returning a node exposes these.

But is recursion the best way to handle this? Since you are simply traversing along a chain a simple loop seems much more effecient:

int minValue()
{
    if (root == nullptr) {
        throw std::runtime_exception("Blaaa");
    }
    node* last = root;
    for(;last->left; last = last->left) {
        /* Do nothing in the body */
    }
    return last->value;
}

The inorder() traversal works.

//Inorder traversal
void inorder(node *tnode){
    if(tnode->left!=NULL){
        inorder(tnode->left);
    }
    cout<<tnode->value;
    if(tnode->right!=NULL){
        inorder(tnode->right);
    }
}

But testing the left and right values before calling makes the code more difficult to read. More traditionally you test to see if the node is null before you start and simply return. Also you simply print the value. Why not pass a function that is called for each value that makes the traversal much ore interesting.

void inorder(std::function<void(int)> action) {
    doInorder(action, root);
}
void doInorder(std::function<void(int)> action, Node* node) {
    if (node == nullptr) {
        return;
    }
    doInorder(action, node->left);
    action(node->vallue);
    doInorder(action, node->right);
}

Then you can call the in-order with a function that prints each value.

tree.inorder([](int v){std::cout << v << " ";});

The insert function is basically correct.

//insert function
node* insert(int val,node *tnode){
    node *temp=tnode;
    if(temp==NULL){
        temp= new node;
        temp->value=val;
        temp->left=NULL;
        temp->right=NULL;
    }
    else if(val<temp->value){
        temp->left=insert(val,temp->left);
    }
    else if(val>temp->value){
        temp->right=insert(val,temp->right);
    }
    return temp;
}

The only difference I would do is make the new a single line.

temp= new node{val, nullptr, nullptr};

The delete node looks great.

These are some very nice points especially the points made on inorder traversal and iterative approach of minimum value.I will also look into encapsulation and try to implement classes in c++ programs. — Anantha Padmanaban
– Anantha Padmanaban, Commented May 17, 2017 at 19:35

miscco · Accepted Answer · 2017-05-17 19:18:57Z

Do not use namespace std; this is a bad practice, that will hurt you in the long run.
In C++ you would generally want to generate classes that represent the objects of your code. So what do you have here?

A binary tree that is composed of nodes. Generally the tree class would handle insertion and removal of nodes. So you should start with 2 classes tree and node. Also a class should have a constructor and optionally a destructor

class node {
    node(const int Value) 
        : value(Value) {}
private:
    int value;
    node* left = nullptr;
    node* right = nullptr;
}

class binaryTree {
public:
    binaryTree() {}
    ~binaryTree(){}

    Insert(const int Value);
    Remove(const int Value);
    Search(const int Value) const;
private:
    node* root = nullptr;
}

Now we have some problems here. The nodes themself are more or less loose, as we only store the pointer to the nodes. You can walk around this, by using smart pointer in this case std::unique_ptr<node>.

Second, we made the nodes private members, so we have to add a member function to the nodes too, that handles insertion, removal or search. There are different possibilities. The cleanest would be to add the appropriate member functions to the node class. The second would be to declare the tree a friend of the node. The third would be to turn the class into a struct and just make them public. Your choice.

For a binary tree you need to compare the values of the nodes with the data you want to put in. This is best done by defining an operator<(const node& otherNode) or operator<(const int Value)
As you might have seen i did not use NULL. In recent C++ we have a keyword for that nullptr so you should use that.
Why does your deleteNode function returns a pointer to a node. You are deleting it. Where should that point to?

Thank you for the feedback.Not using the namespace std is something i have not heard of.I'll look into it.As far as deleteNode is concerned,when i delete a node from the tree,Its parent should point to the deleted node's child thats why i return the pointers.The pointers are deleted node's children and not the deleted node itself. — Anantha Padmanaban
– Anantha Padmanaban, Commented May 17, 2017 at 19:30
@AnanthaPadmanaban See Why is “using namespace std” considered bad practice? — Loki Astari
– Loki Astari, Commented May 17, 2017 at 19:46

Stack Exchange Network

BST implementation in c++

2 Answers 2

Design

Code Review

You must log in to answer this question.

Hot Network Questions

BST implementation in c++

2 Answers 2

Design

Code Review

You must log in to answer this question.

Related

Hot Network Questions