CODEWITHSUNDEEP
c++pointersinsertbinary-search-tree
Frontier
Frontier

Reputation: 149

Binary Search Tree: Issue with Insert Function

I've been researching how to create binary search trees and i have run into a problem when trying to create my own. I have to use the following private structure to create the tree. Every example that i have looked at uses left and right pointers pointing to the structure and i have to use left and right pointers pointing to my template class. I have been trying to figure out how to write the insert function for adding a new node into my tree but i keep running into problems because of the way these two pointers are setup. Does anyone have a clue on how to make it work with these two pointers below?

private:
struct BinaryNode
{
    Comparable element;
    BinarySearchTree<Comparable> *left;
    BinarySearchTree<Comparable> *right;
};
 BinaryNode *root;
};

This is my constructor

BinarySearchTree<Comparable>::BinarySearchTree() {
BinaryNode *temp;
temp = new BinaryNode;

temp->left= NULL;
temp->right= NULL;

root = temp;
}

Upvotes: 1

Views: 141

Answers (1)

user2033018
user2033018

Reputation:

Try the following:

public:
    template <typename Comparable>
    void insert(const Comparable& key)
    {
        root = insert(root, key);
    }

private:
    template <typename Comparable>
    BinaryNode* insert(BinaryNode*& current_node, const Comparable& key)
    {
        if (current_node == nullptr)
        {
            // Create a leaf node and return it, thus attaching
            // it to the node we last called the function with

            return new BinaryNode{key, nullptr, nullptr};
        }

        if (key == current_node->element)
            // duplicate element, take some action
        else if (key < current_node->element)
            current_node->left = insert(current_node->left, key);
        else
            current_node->right = insert(current_node->right, key);

        return current_node;
    }

Upvotes: 1

Related Questions