Inserting an element in Binary Tree

Question

Tried exploring a lot over the net, but could get any help, Everywhere its like adding a node to the Binary Search tree.

Question: Requesting for algorithm and code snippet for adding a node to the Binary tree. ( or point me to correct URL )

Assumption: As per my understanding, Binary Tree and Binary Search Tree is different? Correct me if I am wrong.

( request: if you are writing your code snippet please use proper variable name, that helps in understanding )

Eg: Binary Tree

5 7 3 x1 x2 x3

                 5

          7               3

   x1       x2       x3

Binary Search Tree 5 7 3 2 4 6

                   5
          3               7

   2          4       6       





insert(int key, struct node **root)
{
    if( NULL == *root )`
    {
        *root = (struct node*) malloc( sizeof( struct node ) );`
        (*root)->data = key;
        (*root)->left = NULL;    
        (*root)->right = NULL;  
    }
    else if(key < (*root)->data)
    {
        insert( key, &(*root)->left );
    }
    else if(key > (*root)->data)
    {
        insert( key, &(*root)->right );
    }
}

If you are talking about binary search tree and if you are trying to do some instertion, maybe this could help?: en.wikipedia.org/wiki/Binary_search_tree#Insertion — CLearner
– CLearner, Commented Apr 30, 2013 at 5:33
@AbdullahShoaib Tell me what will be the right order of BST. — Raa
– Raa, Commented Apr 30, 2013 at 16:33
@Cleaner : insertHelper() at the given link also checks for the value < node->key , where as Binary tree should not bother whether the value is less or greater. it should go ahead and place the next node to left if its available or else to right. I hope you understand whats the difference between Binary tree and Binary Search Tree is? according to that do you think its correct. — Raa
– Raa, Commented Apr 30, 2013 at 16:37
@wildplasser : yes its a BST , I am looking for the Binary tree.. not getting an algorithm to do the same — Raa
– Raa, Commented Apr 30, 2013 at 20:18

sbru · Accepted Answer · 2016-09-27 19:25:48Z

9

The difference between a Binary Tree and a Binary Search Tree is that though they both have restrictions that each node can have at most 2 child nodes, a Binary Search Tree (BST) also must have its left child be of equal or lesser value and the its right child must be of greater or equal value. This is why it is called a "Search" tree because everything is ordered numerically and it has an O(logn) run time for searching.

Because there isn't the requirement of being a BST, a Binary Tree can be stored in a vector (array). As you insert into the vector you build the Binary Tree in level-order fashion. The code is below:

// typedef the node struct to NODE
// nodeVector similar to STL's vector class
insert(int key, NODE** nodeVector)
{
    NODE *newNode = (NODE*) malloc( sizeof( NODE ) );
    newNode->data = key;
    newNode->left = NULL;    
    newNode->right = NULL;

    // add newNode to end of vector
    int size = nodeVector->size();
    nodeVector->push_back(newNode);

    // if newNode is not root node
    if(nodeVector->size() > 1)
    {
        // set parent's child values
        Node* parent = (size/2)-1; // take advantage of integer division instead of using floor()
        if (parent->left == NULL)
        {
            parent->left = newNode;
        }
        else
        {
            parent->right = newNode;
        }
    }
}

edited Sep 27, 2016 at 19:25

answered Apr 30, 2013 at 7:05

sbru

8876 gold badges21 silver badges36 bronze badges

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

8 Comments

Raa Over a year ago

Thanks for the clarification @bagel. I have updated my BST code for insertion, can you please suggest what changes should i incorporate to make this BST to Binary tree

sbru Over a year ago

post the code you are currently using and I'll see what I can do.

Raa Over a year ago

just posed it in the question, as i was a bit struggling to get it formatted. please ignore ` character.

Raa Over a year ago

what should my left value when I am calling the insert() function from my main ?

sbru Over a year ago

@Ravi you are correct. To be fair, a Binary Tree (or BST for that matter) has no requirements on being balanced so technically this isn't incorrect. If that is an additional requirement you want in your BST then take a look at AVL trees. That being said, you are totally in the right having issues with my code because this is almost identical to a linked list. So now, with another 2 years of education under my belt I will attempt to provide a more desirable solution. :)

|

user905 · Accepted Answer · 2016-05-10 02:57:57Z

3

A Queue data structure can be used for inserting element in to a Binary Tree, since in Binary Tree the order of nodes is not maintained so we will insert the node as soon as we find any null. Using Queue we will be traversing the Binary Tree in Level Order Traversal.

struct Treenode* temp;

Q = CreateQueue();
EnQueue(Q,root);

while(!IsEmptyQueue(Q))
{
    temp = DeQueue(Q);
    if(temp->left)
        EnQueue(Q,temp->left);
    else
    {
        temp->left=newNode;
        DeleteQueue(Q);
        return;
     }
     if(temp->right)
        EnQueue(Q,temp->right);
    else
    {
        temp->right=newNode;
        DeleteQueue(Q);
        return;
     }
}

edited May 10, 2016 at 2:57

answered May 10, 2016 at 2:47

user905

2604 silver badges14 bronze badges

Comments

codeFreak · Accepted Answer · 2014-06-05 20:20:45Z

0

Since, I cannot comment I am writing this.
The above answer for binary tree insert function is wrong.
Suppose for 0, 1, 2 , 3, 4 , 5 passed in sequence to insert function,
its generating tree like

of which inorder traversal will be 1 3 5 4 2 0
while answer should be

of which inorder traversal will be 3 1 4 0 5 2.

answered Jun 5, 2014 at 20:20

codeFreak

1649 bronze badges

3 Comments

sbru Over a year ago

You are correct, upon coming back to this answer 1.5 years further through my degree I see my mistake :). I'll attempt to fix the issue. Thanks

sbru Over a year ago

Ok, I've made some changes, what are your thoughts on it now?

Ravi Over a year ago

@bagelboy: I still have issues with your code. I am commenting under your post directly.

anonymous · Accepted Answer · 2014-07-26 04:30:26Z

0

Since I also face the same problem, I came up with following solution over the net :-

You can use a queue to store the current node where we want to place the new node as we do in level order traversal and then we insert the nodes level by level.

Following link might help you :-

http://www.geeksforgeeks.org/linked-complete-binary-tree-its-creation/

answered Jul 26, 2014 at 4:30

anonymous

91 bronze badge

Comments

takesavy · Accepted Answer · 2014-12-18 18:25:03Z

-1

I am posting this as answer because I dont have the necessary reputation to post a comment. Except for bagelboy all others have misunderstood the tree as either Binary Search Tree or Complete Binary Tree. The question is simple Binary Tree and Bagelboy's answer looks correct.

edited Dec 18, 2014 at 18:25

answered Dec 18, 2014 at 15:09

takesavy

1432 silver badges17 bronze badges

Collectives™ on Stack Overflow

Inserting an element in Binary Tree

5 Answers 5

8 Comments

Comments

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

8 Comments

Comments

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related