Add node to binary search tree

Question

The following code should add a node to my BST structure, but fails to do so. New nodes simply dont get attached to the tree, including the root node. Could anyone point out where the problem is?

The constructor for the tree:

template <typename K, typename T>
MyBinaryTree<K, T>::MyBinaryTree() {
    root = nullptr;
}

Function that gets called from the outside:

    template <typename K, typename T>
void MyBinaryTree<K, T>::addValue(K key, T value) {
    Node *node = new Node(key, value);
    addToSubtree(root, node);
}

And the internal private function which has to attach the node:

    template <typename K, typename T>
void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node *node,
            MyBinaryTree<K, T>::Node *toAdd) {
    if(node == nullptr) {
        node = toAdd;
    } else {
        if(toAdd->key > node->key) addToSubtree(node->right, toAdd);
        else if(toAdd->key < node->key) addToSubtree(node->left, toAdd);
    }
}

fghj · Accepted Answer · 2015-10-25 16:26:39Z

1

You should use references, like this:MyBinaryTree<K, T>::Node *&root

because of when you modify root in addToSubtree, it modify only local function parameter root, copy of root parameter, not root parameter by itself.

answered Oct 25, 2015 at 16:26

fghj

9,4744 gold badges37 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

dreamzor · Accepted Answer · 2015-10-25 16:26:07Z

0

Your node variable is a local variable containing pointer to Node, when you assign a value to it, it only works for that local variable in function scope.

To make your function work, you should make a node variable pointer to pointer (so it gets called like addToSubtree(&node->right, toAdd) or reference to pointer.

answered Oct 25, 2015 at 16:26

dreamzor

5,9454 gold badges44 silver badges62 bronze badges

Comments

David Haim · Accepted Answer · 2015-10-25 16:35:58Z

0

Your code suffers from two problems:

Although it's supposed to represent Object-Oriented thinkig, the code falls back to C-style of doing things. the root element should not be passed as argument. it exists automaticallty in every member function scope since it's a member variable.

this :

   template <typename K, typename T>
void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node *root,
            MyBinaryTree<K, T>::Node *toAdd) {
   //rest...
}

should be this :

   template <typename K, typename T>
void MyBinaryTree<K, T>::addToSubtree( MyBinaryTree<K, T>::Node *toAdd) {
    if(root == nullptr) {
        root = toAdd;
    } //rest...
}

The function already knows what root is since root is a member variable. member functions can change member variables without of them needing to be passed into the function

The real problem is the difference between pointer to pointer to pointer. whenever we want a function to change one of the arguments given, that argument should be passed either as pointer or as a reference.

if the argument is already a pointer ,in order to change the pointer itself it should be passed either as pointer to pointer or a referene to pointer

so, let's assume we do want to continue pass root as an argument (we don't), we should pass it either as

void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node **root,
            MyBinaryTree<K, T>::Node *toAdd) {
    if(*root == nullptr) {
        *root = toAdd;
        //rest

either as

void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node*& root,
            MyBinaryTree<K, T>::Node *toAdd) {
    if(root == nullptr) {
        root = toAdd;
       //the rest...

the second is more C++ style, the first is more C style, but both are valid.

edited Oct 25, 2015 at 16:35

answered Oct 25, 2015 at 16:30

David Haim

26.7k4 gold badges50 silver badges88 bronze badges

2 Comments

Whizzil Over a year ago

root is passed as an argument since it needs it for the recursive calls, how should I call addToSubtree(Node *& toAdd) recursively into the subtrees of the root then?

David Haim Over a year ago

I think that addToSubTree should be a member function of Node in the first place then you won't have this problem: root->left.addToSubTree(newNode) then it recourse as a member functionb

Collectives™ on Stack Overflow

Add node to binary search tree

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related