0

Is there any way to insert a new node in a binary tree (not bst) without comparing key values? The following code only works for the very first three nodes. 

node *insert (node *root, int *key) {

if (root==NULL) {
    root=newNode(root, key);
    return root;
}

else if (root->left == NULL)
    root->left=insert(root->left,key);
else if  (root-> right == NULL)
    root->right=insert(root->right,key);

return root;

}
nawh
  • 1
  • 1
    Insert elements into an array and make a min/max heap out of it, using index values. The resulting tree will be a binary tree. – taurus05 Feb 05 '19 at 18:43
  • Simple implement min/max heap. – Anuj Vishwakarma Feb 05 '19 at 18:44
  • Thank you, but don't min/max heaps have restrictions on the root value (i.e. it must be the minimum or the maximum)? – nawh Feb 05 '19 at 18:55
  • To be clear, you just want some key arbitrarily inserted into a tree? – Daniel Feb 05 '19 at 18:56
  • Yes, the key values are actually pointers, rather than integers. When a key is created, it should go to the first available space. – nawh Feb 05 '19 at 19:00
  • While I made an answer, perhaps I'm missing the point. What are you actually trying to achieve by using a tree? What purpose are you trying to use it to serve? – Daniel Feb 05 '19 at 19:03

5 Answers5

1

If you change 

else if  (root-> right == NULL)

to just 

else

Then it would have the effect of always adding to the right.

If you want it to randomly pick, add a call to srand outside this function. 

srand(time(NULL));

Then in this function, call 

else if (rand() > MAX_RAND / 2) {
    root->right = insert(root->right, key);
} else {
    root->left = insert(root->left, key);
}

at the end of your existing if/else structure.

See also:

If your tree tracks its height at each node, you could add after your null checks something like 

else if (root->left->height <= root->right->height) {
    root->left = insert(root->left, key);
} else {
    root->right = insert(root->right, key);
}

That would keep the tree balanced automatically. But it requires additional code to manage the height. E.g. 

root->height = 1 + ((root->left->height > root->right->height) ? root->left->height : root->right->height);

I leave it up to you whether that additional overhead is worth it.

The people suggesting using a heap are suggesting using the indexes as the ordering. This is kind of useless as a heap, but it would make a balanced binary tree. So the root node would be the first inserted and the most recent inserted would be the rightmost leaf.

mdfst13
  • 850
  • 8
  • 18
1

You could just keep track of the height of each node, and always insert it into the side with fewer children:

node *insert (node *root, int *key) {
    if (root==NULL) {
        root=newNode(root, key);
        root->height = 0
    }
    else if (root->left == NULL) {
        insert(root->left,key);
    }
    else if (root->right == NULL) {
        insert(root->right,key);
    }
    else if (root->left->height <= root->right->height) {
        insert(root->left,key);
    } else {
        insert(root->right,key);
    }
    root->height++
}
dave
  • 62,300
  • 5
  • 72
  • 93
  • As written, what you are calling height actually holds the size of the tree (or subtree). I say this because you always increment the value on `insert`. It will work with size, but it would be better to use the [more common terminology](https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology_used_in_trees). Height measures how many levels of children there are. What you're measuring is the total number of descendants. – mdfst13 Feb 06 '19 at 00:40
0

In

else if (root->left == NULL)
  root->left=insert(root->left,key);

you know root->left is NULL so why to do the recursive call ?

Of course same for the next else

The following code only works for the very first three nodes.

If both left and right are non NULL you do not insert, that time it was necessary to do the recursive call on one of the two branches, and you will consider the key (so insert ordered) to decide which one. Note that the 2 tests to NULL you did are not correct if you insert to have a sorted tree ...

bruno
  • 32,421
  • 7
  • 25
  • 37
0

Comparing values is actually irrelevant, the only think you need to do is set a pointer. Since you didn't specify any real requirements, one solution could be as follows:

Changing the signature a bit so now you have a pointer to an already allocated node:

void insertNode(node *&root, node *newNode) {
    if (root == NULL) { 
         root = newNode;
         return;
    }
    if (root->left == NULL) {
        root-left = newNode;
        return;
    }
    helperInsert(root->left, newNode);
    return;
}

This will set the head (assuming I got the signature right), and otherwise check the left child. 

void helperInsert(node *it, node *newNode) {
    if (it->left == NULL) {
        it->left = newNode;
        return;
    }
    helperInsert(it->left, newNode);
    return;
}

This is obviously a flawed approach (the tree will not be balanced at the slightest), almost treating the tree as a linked list, but to my best understanding of the question, this is an example of how it can be done.

Daniel
  • 854
  • 7
  • 18
  • Thank you very much, will try this asap. – nawh Feb 05 '19 at 19:03
  • The signature of `node *&root` could be dead wrong, as a heads up. If that fails, a pointer to the root pointer would also be a pragmatic solution. Also, this basically treats the tree like a linked list, so it might not really be what you're looking for. – Daniel Feb 05 '19 at 19:05
0

The heap advice is most sound. You don't need to heapify anything, just follow the rules that an element at index k has children at 2*k + 1 and 2*k + 2.

Another approach, useful when there is no array, but the nodes are generated on the fly, is to fill the tree level-wise. Notice that at level k there are 2 ** k slots, conveniently indexed by a k-bit integer. Interpret the index as a path down the tree (clear bit tells to follow left child, set bit tells to follow a right one), along the lines of:

        void insert_node(struct node * root, struct node * node, unsigned mask, unsigned path)
        {
            while ((mask >> 1) != 1) {
                root = mask & path? root->right: root->left;
            }
            if (mask & path) {
                assert (root->right == NULL);
                root->right = node;
            } else {
                assert (root->left == NULL);
                root->left = node;
            }
        }

        void fill_level_k(struct node * root, unsigned k)
        {
            unsigned slots = 1 << k;
            for (unsigned slot = 0; slot < slots; slot++) {
                struct node * node = generate_new_node();
                insert_node(root, node, slots, slot);
            }
        }
user58697
  • 7,808
  • 1
  • 14
  • 28