Why code create wrong Binary search tree

Question

I am trying to create a Binary search tree sicne morning and i am still not able to do, I get wrong output when i see the tree formed on debugging then it is not correct.

How i do ?

(1) I have an array of values which will be data of each node in tree.
(2) I create the root node and pass that node in CreateBinarySearchTree(&RootOfTree, values, size); function.
(3) In  CreateBinarySearchTree(Tree**RootOfTree, int* values, int size) definition  i have 4 conditions:

if ((*RootOfTree)->left == NULL && (*RootOfTree)->right == NULL){...}
else if ((*RootOfTree)->left == NULL && (*RootOfTree)->right != NULL){..}
else if ((*RootOfTree)->left != NULL && (*RootOfTree)->right == NULL){..}
and else{ CreateBinarySearchTree(&(*RootOfTree)->left, values, size);}  

My full code is here :

       // BinaryTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <array>
using namespace std;

struct Tree
{
    Tree*left = NULL;
    Tree*right = NULL;
    int data;

};
int counte = 0;
int values[] = { 8, 5, 4, 9, 7, 11, 1, 12, 3, 2 };
int val = values[counte];
Tree*storeRoot = NULL;
int _tmain(int argc, _TCHAR* argv[])
{
    Tree *tree = NULL;
    void CreateBinarySearchTree(Tree**RootOfTree, int* values, int size);

    int size = sizeof(values) / sizeof(values[1]);
    Tree* RootOfTree = NULL;
    if (tree == NULL)
    {
        tree = new Tree();
        RootOfTree = tree;
        tree->data = values[0];
        tree->left = NULL;
        tree->right = NULL;
    }
    storeRoot = RootOfTree;
    CreateBinarySearchTree(&RootOfTree, values, size);
    return 0;
}

void CreateBinarySearchTree(Tree**RootOfTree, int* values, int size)
{

    Tree *tree = NULL;
    if (counte > size)
    {
        return;
    }

    if ((*RootOfTree)->left == NULL && (*RootOfTree)->right == NULL)
    {
        counte++;
        val = values[counte];
        tree = new Tree();
        tree->data = val;
        tree->left = NULL;
        tree->right = NULL;
        if ((*RootOfTree)->data < val)
        {
            (*RootOfTree)->right = tree;
        }
        else if ((*RootOfTree)->data > val)
        {
            (*RootOfTree)->left = tree;
        }
        CreateBinarySearchTree(&(*RootOfTree), values, size);
    }
    else if ((*RootOfTree)->left == NULL && (*RootOfTree)->right != NULL)
    {
        counte++;
        val = values[counte];
        if ((*RootOfTree)->data > val)
        {
            tree = new Tree();
            tree->data = val;
            tree->left = NULL;
            tree->right = NULL;
            (*RootOfTree)->left = tree;
        }
        else
        {
            counte--;
            CreateBinarySearchTree(&(*RootOfTree)->right, values, size);
        }
    }
    else if ((*RootOfTree)->left != NULL && (*RootOfTree)->right == NULL)
    {
        counte++;
        val = values[counte];
        if ((*RootOfTree)->data < val)
        {
            if (storeRoot->data > val)
            {
                tree = new Tree();
                tree->data = val;
                tree->left = NULL;
                tree->right = NULL;
                (*RootOfTree)->right = tree;
            }
            else
            {
                if (storeRoot->right == NULL)
                {
                    tree = new Tree();
                    tree->data = val;
                    tree->left = NULL;
                    tree->right = NULL;
                    (storeRoot)->right = tree;
                }
                else
                {
                    counte--;
                    CreateBinarySearchTree(&storeRoot, values, size);
                }
            }
        }
        else
        {
            counte--;
            CreateBinarySearchTree(&(*RootOfTree)->left, values, size);
        }
    }
}

Please correct me wherever i am wrong so that it will create binary searach tree. Please also give detail explanation while answering, Thanks

Answer 1

Let's start from the top. What is a binary search tree (BST)? A binary search tree is a data structure where each node to the left of a given node contains a value smaller than it and each node to the right of a given node contains a value greater than it. The binary search tree also has a single root node.

Take a look at your code. You're thinking that the root of a tree is a tree itself (root of tree is a Tree type). This is incorrect; the root of a tree is a node. Each node stores a value, and two pointers to other nodes: its left and right children. Let's translate that into code:

class BST {

public:
    BST() : head(nullptr) {}
    ~BST() { /* Implement */ }
    void insert(int value);
private:
    struct Node{
        Node(int d, Node *l = nullptr, Node *r = nullptr) : data(d), left(l), right(r) {} 
        int data;
        Node *left, *right;
    } *head;
    void insert(Node *n, int val);
};

Now, onto your insertion algorithm. Your creation function should handle all the details of creating the tree. That is, your user really shouldn't be responsible for creating the tree and passing it in. That would be contradictory to the name of your function. Moreover, your function creates too many subcases that could easily be generalized. We want to check for three things:

1. Is the tree empty (e.g. is the root pointing to nullptr)?
2. If it is, populate the root and return.
3. Otherwise, check the insertion value and recurse down the tree until you get to a suitable location for the value.

You can easily implement this using our new OOP design and delegate the actual insertion to a private member function. The reason we do that is because we only want to modify the head pointer when we're changing what it points to (either when the tree is empty and we're populating it or when we're destroying the tree). In all other cases, we want the head pointer to simply be a starting point for our insertion function. Delegating our insertion to a private insertion function taking the head as a pointer will copy the head pointer and therefore not modify the original one:

void BST::insert(int value) 
{
    insert(head, value);
}

void BST::insert(Node *n, int val)
{
    if (!head) {
        head = new Node(val);
        return;
    }

    if (val < n->data) {
        if (n->left)
            insert(n->left, val);
        else
            n->left = new Node(val);
    } else if (val > n->data) {
        if (n->right)
            insert(n->right, val);
        else
            n->right = new Node(val);
    }
}