Binary search tree methods

Question

I have implemented a binary search tree with the methods search, insert, and delete. I want to know if this is the best way to code them or if there are any other way by which I can reduce the code size or redundancies in code, if any.

#include <bits/stdc++.h>
using namespace std;

struct node{
    int val;
    node* left;
    node* right;
    node(){
        left=right=NULL;
    };
    node(int val){
        this->val = val;
        left=right=NULL;
    }
};

struct bTree{
    node* root;
    void insert(int val);
    node* search(int val);
    void deleteVal(int val);
    node* getParent(int val);
    bTree(){
        root = NULL;
    }
    bTree(int val){
        root = new node(val);
    }
};

void bTree::insert(int val){
    if(!root){
        root = new node(val);
        return;
    }
    node* temp = root;
    node* parent = root;
    while(temp){
        parent = temp;
        if(val >= temp->val){temp = temp->right;}
        else{ temp = temp->left;} 
    }
    if(val >= parent->val){parent->right = new node(val);}
    else{parent->left = new node(val);}
    return;
}

node* bTree::search(int val){
    node* temp = root;
    while(temp && (temp->val!=val)){
        if(val > temp->val){temp = temp->right;}
        else if(val < temp->val){temp = temp-> left;}
    }
    return temp;
}

node* bTree::getParent(int val){
    if(!root || (root->val == val)){return NULL;}
    node* temp = root;
    node* parent = NULL;
    while(temp){
        if(temp->val == val) return parent;
        if(val < temp->val) {parent = temp; temp= temp->left;}
        if(val > temp->val) {parent = temp; temp= temp->right;}
    }
    return NULL;
}


void bTree::deleteVal(int val){
    node* temp = search(val);
    if(!temp){return;}
    if(!(temp->left) && !(temp->right)){
        if(temp==root){
            root = NULL;
            delete temp;
        }
        else{
            node* parent = getParent(val);
            if(parent->right==temp){parent->right=NULL; delete temp;}
            else{parent->left=NULL; delete temp;}
        }
    }
    else if(!(temp->left) && (temp->right)){
        if(temp==root){
            root = root->right;
            delete temp;
        }
        else{
            node* parent = getParent(val);
            if(parent->right==temp){parent->right=temp->right; delete temp;}
            else{parent->left = temp->right; delete temp;}
        }
    }
    else if((temp->left) && !(temp->right)){
        if(temp==root){
            root = root->left;
            delete temp;
        }
        else{
            node* parent = getParent(val);
            if(parent->right==temp){parent->right = temp->left; delete temp;}
            else{parent->left = temp->left; delete temp;}
        }
    }
    else{
        node* minNode =temp->right;
        while(minNode->left){
            minNode = minNode->left;
        }
        int valStoring = minNode->val;
        deleteVal(minNode->val);
        temp->val = valStoring;
    }
    return;
}

int main(){
    bTree a;
}

Answer 1

In Addition to what @Mast said.

You DON'T implement the rule of three.
This needs to be fixed (especially since you have resource ownership).

Missing Destructor.

I think you can simplify some of your code by moving it from btree into node and using some simpler functions that do specific parts of the task.

There is an extra default constructor in node that I think is superfluous. When are you going to create a node with the value undefined?

You should be using nullptr rather than NULL. Its 2015 the standard has been out 4 years and every modern compiler now supports it.

It is more standard to use an initial capitol letter for types (to help spot them). And use an initial lower case letter for objects (this includes functions and methods).

Thus node => Node and btree => BTree

I don't like your delete it is overly complex. You should never need to find the parent of a node when doing tree manipulation. You had to pass it to get to the current node.

As a side note. This can be trivially templatized to handle any type.

insert

You don't check for equivalence. I presume this is bug (because the second one will never be found anyway).

Can be simplified like this:

void bTree::insert(int newVal){
    if(!root){
        root = new node(newVal);
        return;
    }
    root.insert(newVal);
}
void node::insert(newVal) {

    if (val == newVal) {
        return;
    }
    if (newVal < val) {
         left = insertNext(left, newVal);
    } else {
         right = insertNext(right, newVal);
    }
}
node* node::insertNext(Node* next, int newValue) {
    if (next == nullptr) {
       return new node(newValue);
    }
    next.insert(newValue);
}

deleteVal

void bTree::deleteVal(int delVal){
    if (!root) {
        return;
    }
    node*  bad = nullptr;
    root = root.deleteVal(bad, delVal);

    //  This assumes node does not own its left/right members.
    delete bad;
}
node* node::deleteVal(node*& bad, int delVal) {
    /*
     * Note: If this function does not return this.
     *       Then we have removed it from the tree.
     *       we will return one of the subtrees instead
     *       potentially modified.
     */
    if (val == delVal) {
        bad = this;
        if (left == nullptr) {
            // If the left subtree is null then the right is the one we want (even if null)
            return right;
        } else if (right == nullptr) {
            // If the right subtree is null then the left is the one we want
            return left;
        } else {
            // Otherwise both subtrees are not null.
            // Now we must do some work.
            // Rotate the right sub tree up into this place.
            // Thus move the left subtree to the leftmost node in the right subtree.
            addLefttoRightSubTree(left, right);
            return right;
        }
    // Otherwise ask the next node to do the work.
    } else if (delVal < val) {
        left = deleteValNext(left, bad, delVal);
    } else
        right = deleteValNext(right, bad, delVal);
    }
    return this;
}
node* node::deleteValNext(node* next, node*& bad, int delVal) {
    if (next != nullptr) {
        return next.deleteVal(bad, delValue);
    }
    return nullptr;
}

Answer 2

Namespace

#include <bits/stdc++.h>
using namespace std;

The first line supposedly inserts all includes your code needs but haven't specifically included. The second line saves you a lot of typing by not having to insert std:: in front of all relevant methods and types.

Please don't use those!

Read Why is “using namespace std;” considered bad practice? on Stack Overflow for the full read, but the short version is it's a major maintainability risk and allows function conflicts to arise.

The first line combined with the second line makes it even worse, since now you are no longer in control about how your code executes. You should tell the compiler what to do, not the other way around.

You current style not only hurts maintainability, it also hurts your understanding of how the language works. Practices like these lead to programmers not understanding how to make the best of namespaces.

Style

left=right=NULL;`

This hurts readability and maintainability. It's clear you're setting something to NULL, but not why. You're probably resetting something. However, you're resetting both left and right at the same time, on the same line. If you need to reset multiple things at the same time, you usually implement a function doing so.

if(val < temp->val) {parent = temp; temp= temp->left;}`

All your if statements look like that. The more accepted (and more readable) style of bracketing in C++ goes like this:

if(val < temp->val)
{
    parent = temp;
    temp= temp->left;
}

Don't be afraid of using newlines.

int main(){
    bTree a;
}

You declare a bTree named a. You're not doing anything with it, just creating something. If you would do something with it, you'd notice a isn't a good name for a bTree. a.insert(val) doesn't tell me anything, except you're inserting something into a. In a bigger project, you'll encounter more variable names and all those names should be descriptive.

Finally:

The size of code in C++ is usually irrelevant. Space is cheap nowadays and saving a couple of bytes in the source won't bring you anywhere with compiled languages. Only the size of the resulting binary may be relevant, especially if you're working on embedded systems.