Thursday, June 27, 2013

Binary search tree insertion

A Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. The number of nodes in the left subtree and right subtree of the root respectively is
a)  (4, 7)      b)  (7,4)     c)  (8,3)   d)   (3,8)

Binary search tree(BST), is also called an ordered tree or sorted binary tree, is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
The left and right subtree must each also be a binary search tree and their must be no duplicate nodes.

Suppose x is a node in a binary search tree and y is another node in the left subtree of x, then y.key < x.key. If y is a node in the right subtree of y then x.key < y.key.

Insertion begins as a search would begin; if the key is not equal to that of the root, we search the left or right subtrees. Eventually, we will reach a null pointer and add the new node to the leaf node (trailing pointer) as its right or left child, depending on the leaf node's key.
   
Let us insert the elements into a binary search tree in sequence 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24.  







Algorithm: Tree-Insert(T, z)
{
// Algorithm to insert z in T, where x, y, z are nodes
// and x.key is the value of node x, x.right is the right pointer of x
 

y = NULL;
x = T.root;


//Searches x in T
while(x != NULL)
{
    y = x; //y is the trailing pointer
    if(z.key < x.key)
       x = x.left;
    else
       x = x.right;
}


// z is added to the trailing pointer depending on y's value
if (y == NULL)
    T.root = z; //Tree T was empty
else if(z.key < y.key)
    y.left = z;
else
    y.right = z;
}

Running time: O(h) , where h is the height of the tree.

When we look at the final tree that has been generated, the answer will be b) (7, 4). 

Just looking at the sequence 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24, we know that 50 is inserted as the root node,  the elements less than 50 would go into the left subtree of  50 and the elements more than 50 would go into the right subtree of 50. All that we have to do is count the integers less than 50 and the integers more than 50.

Share your thoughts in the comments below, to make me describe the blog post  even better and do recommend the post if you found the content helpful!!!

3 comments:

  1. We Provide Our Customers With Latest and up-to-date Dumps Questions & Answers with 100% Exam Passing Guarantee. We Promise Exceptional Success in First Attempt. N10-007 Exam Practice Test

    ReplyDelete
  2. This particular papers fabulous, and My spouse and i enjoy each of the perform that you have placed into this. I’m sure that you will be making a really useful place. I has been additionally pleased. Good perform! recover lost bitcoins

    ReplyDelete
  3. This is a great experience of why recover money invested in bitcoin the financial market monetarists have it right. Inflation is not a useful measure to guide financial policy. Thanks for sharing,

    ReplyDelete