Binary search tree deletion

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. Show the result binary search tree after the elements have been deleted in the order 20, 12, 37, 5, 62, 50, 8.

Three possible cases occur when we delete an element of a Binary Search Tree. Deletion of an element should preserve the BST property.

Let the node to be deleted be x.

Case  1: x has no children.

             Delete x by making parent of x point to NULL. Parent of x can be obtained through a trailing pointer.

Case 2: x has one child.

             Delete x by making parent of x point to x's child, then delete x.

The case 1 and case 2 are simpler compared to the third case, case 3 is a bit trickier.

Case 3: x has two children.

            To preserve the binary search tree property we need to copy the immediate successor of x to x's place. The immediate successor of x can be found in right subtree of x. The immediate successor is also the minimum element in the right subtree of x.  Let the immediate successor be y. First we need to search this minimum element y. After we have copied y to x's place, we will have a binary search tree (and the BST property preserved) with duplicates.  y element is at two places and we need to delete the y in the original place. Deleting the y in original place will be either case 1 or case 2.  Deleting y in the original place cannot be case 3 because it is the minimum element in a binary search tree subtree, the minimum element has always one child or no child.          

Searching the minimum element in right subtree involves traversing the left pointers from the root node of the subtree. The last non NULL node gives the minimum element in the right subtree of x.

Briefly, copy the minimum element y in the right subtree of x to x's place. Delete the y in original place through case 1 or case 2.

The Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. Now let us delete the elements in the order 20, 12, 37, 5, 62, 50, 8.

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!!!

Read More

Number of nodes in a complete binary tree

How many nodes are there in a full complete binary tree of level 6?

a) 40             b) 31               c) 127               d) 128

A binary tree's level starts at 0,  a full complete binary tree has 2^i nodes at level i. At level 0 there is 1 node, at level 1 there are 2 nodes and  it goes on.

There are 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 = 2 ^ (6+1) - 1 = 2^7 - 1 = 127 nodes.

A level is also called the height of the binary tree. In a full complete binary tree of height 'h' there are 2^(h+1) - 1 nodes.

2^0+ 2^1+ 2^2 + 2^3+...................... +2^h = 2^(h+1) - 1

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are filled in left to right order.

In a complete binary tree of height 'h' there can be [2^h  2^(h+1) - 1] nodes.  A complete binary tree can have 2^h minimum number nodes or 2^(h+1)-1 maximum number of nodes.

In a complete binary tree of height 2, there can be 4 minimum number of nodes and 7 maximum number of nodes. 

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!!!

Read More

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!!!

Read More

Relation between leaf nodes and non leaf nodes in a Binary Tree

A Binary tree has n leaf nodes. The number of nodes of degree 2 in T is:

a) log₂ n         b)  n-1          c) n             d) 2^h

The answer is b) n-1

Let n1 be the number of nodes of degree one

n0 be the number of nodes of degree 0,  leaf nodes are the ones which have degree 0

n2 be the number of nodes of degree 2,  root node is one example of a degree 2 node in the figure below.

n be the total number of nodes in the tree.

we have,   n = n0 + n1 + n2                                                     -------------  1

If we count the number of edges in a binary tree, we see that every node except the root has an incoming edge into it. If E is the number of edges, then n = E + 1, i.e. number of edges in a binary tree is one less than the total number of nodes.

Each n0 node contributes no edge,

each n1 node contributes one edge,

and each n2 node contributes 2 edges to the total number of edges, E.

E = 0*n0 + 1 * n1 + 2* n2

E = n1 + 2n2 

                                                                       

We know that n = E + 1

n = n1 + 2n2 + 1                                                                     -------------- 2

Solving equations 1 and 2, we get

n0 + n1 + n2 = n1 + 2n2 + 1

n0 = n2 + 1

The number of leaf nodes in a binary tree is one more than the number of degree 2 nodes.

In the above binary there are 6 nodes in total, n = 6

We know that n = n0 + n1 + n2

n = 3 + 1 + 2

Also we know that n  = E + 1

E is the total number of edges, E = 5, every node has one incoming edge except the root node.

E = n1 + 2n2

n1 = {2} , which contributes edge 'c'

n2 = {1, 3}, node 1 contributes edges 'a' and 'b',  node 3 contributes edges 'd' and 'e'.

n0  = {4,5,6} doesn't contribute any edge.

E = 1 + 2 * 2 = 5

n = E+ 1 = 6

n0 = n2 + 1 = 2 + 1 = 3

In a ternary tree we have n = n0 + n1 + n2 + n3                   ------------- 3

n3 is the number of nodes of degree 3.

If we count the number of edges in a ternary tree, we see that every node except the root has an incoming edge into it. If E is the number of edges, then n = E + 1, i.e. number of edges in a ternary tree is one less than the total number of nodes.

Each n0 node contributes no edge,

each n1 node contributes one edge,

each n2 node contributes 2 edges,
each n3 node contributes 3 edges to the total number of edges, E.

E = 0*n0 + 1 * n1 + 2* n2 + 3* n3

E = n1 + 2n2 + 3n3 

                                                                       

We know that n = E + 1

n = n1 + 2n2  + 3n3 + 1                                                      -------------- 4

Solving equations 3 and 4, we get

n0 + n1 + n2 +n3= n1 + 2n2 + 3n3 + 1

n0 = n2 + 2n3 + 1                                                              -------------- 5

The number of leaf nodes in a ternary tree of n nodes, with each node having 0 or 3 children is

 n0 = n2 + 2n3 + 1

 n2 = 0, n1 = 0 as there are only nodes having degree 0 or degree 3

 then n0 = 2n3 + 1

we know that n = n0 + n1 + n2 + n3

n = (2n3 + 1) + 0 + 0 + n3

n3 = (n - 1) / 3

then n0 = 2n3 + 1 = 2 ((n-1)/3) + 1 = (2n + 1) / 3 

In an m'ary tree we have n = n0 + n1 + n2 + n3 + ........... +n_m

Equation 5 can be generalised to 

n0  = n2 + 2n3 + 3n4 + .........  + (m-1)n_m + 1

The number of leaf nodes in a m'ary tree of n nodes, with each node having 0 or m children is

n1= 0, n2 = 0, n3 = 0,.........................n_m-1 = 0 as there are only nodes having degree 0 or m

n0 = 0 + 0 + 0 +.............. (m-1)n_m + 1

n0 = (m-1)n_m + 1

we know that n = n0 + n1 + n2 + n3 + ........... +n_m

n = ((m-1)n_m + 1) + 0 + 0 +..................................+ n_m

n = m*n_m  + 1

n_m = (n - 1) / m

then n0 = (m-1)n_m + 1  = ((m-1) (n-1) / m )+ 1 = (m*n -m -n + m + 1) / m

n0 = (m*n - n + 1) / m  

For the other derivation of this formula look at here.

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!!!

Read More

Ternary tree leaf nodes

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is 

a) n/2      b) (n-1)/3  c) (n-1)/2  d) (2n+1)/3


The answer is: d) (2n+1) / 3

Let us derive the answer assuming the ternary tree a full ternary tree. 

The maximum number of nodes in a ternary tree with height h is (3^(h + 1) - 1) / 2

(3^(h + 1) - 1) /2  = n
(3^(h + 1) - 1)  = 2n
3^(h + 1)  = 2n + 1
3^h * 3 = 2n+1
3^h = (2n+1) /3

At level h i.e. the number of leaf nodes in a ternary tree is 3^h.

So the number of leaf nodes in a ternary tree of n nodes is (2n+1)/3

The derivation of the formula for the maximum number of nodes in a ternary tree with height 'h' is given here. 

 

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or m children is

The maximum number of nodes in an m'ary tree with height h is (m^(h+1) - 1) / (m - 1). 

(m^(h + 1) - 1) / (m-1)  = n
(m^(h + 1) - 1) = n(m-1)
m^(h + 1) = n(m-1) + 1

m^h *m = n(m-1) + 1
m^h = (n(m-1) + 1) / m
m^h = (nm - n + 1) / m

At level h i.e. the number of leaf nodes in an m'ary tree is m^h.

So the number of leaf nodes in an m'ary tree of n nodes is (nm - n + 1) / m.

Suppose m=2 i.e. a binary tree, the number of leaf nodes in a binary tree of n nodes is (2n - n + 1) / 2 = (n+1)/2.

Actual proof is not this straight forward. Let us consider a ternary tree which is not a full ternary tree but has either 0 or 3 children.

Here the number of nodes on level 0 is 1, on level 2 is 3, on level 3 is 6.  The number of leaf nodes are 7 i.e. on level 1 there is one leaf node and on level 2 there are 6 leaf nodes.

According to the formula the number of leaf nodes is (2n+1)/3.
Here n= 10

(2n+1)3 = (2*10+1)/3 = 21/ 3 = 7 which is the right answer, so how is it possible? A detailed proof is given here.

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!!!

Read More

Gate Exam Information

Graduate Aptitude Test in Engineering (GATE) is an all India examination that primarily tests the comprehensive understanding of various undergraduate subjects in Engineering and Technology. The GATE score of a candidate reflects a relative performance of a candidate. The score is used for admissions to post-graduate engineering programmes (eg. M.E., M.Tech, direct Ph.D.) in Indian higher education institutes with financial assistance provided by MHRD and other Government agencies.  The score may also used by Public sector units for employment screening purposes.

 A valid GATE score is essential for obtaining a financial assistance during Masters programmes and in some cases during direct Doctoral programmes in Engineering/Technology/Architechture, and Doctoral programs in relevant branches of Science in an Institution supported by the MHRD or other Government organizations.  To avail the financial assistance (scholarship), the candidate must first secure admission to a programme in these Institutes, by a procedure that could be different for each institute.  Qualification in GATE is also a minimum requirement to apply for various fellowships awarded by many Government organizations.

Read More

Tree height

The maximum number of nodes in a ternary tree with height h

a. (3^(h + 1) - 1 )/ 3          b. (3^h - 1) / 2         c. (3^h - 1 ) /  3           d. (3^(h + 1) - 1)/ 2

The answer is d. (3^(h + 1) - 1) /2

Ternary tree is like a binary tree where each node can have a maximum of 3 children.

At height 0 there is one node, at height 1 there are 3 nodes, at height 2 there are 3^2 nodes and the sequence goes on,

1, 3, 3^2, 3^3,.........................................3^h

if we solve this geometric progression, the answer will be (3^(h + 1) - 1) / (3 - 1)  = ( 3^(h + 1) - 1) / 2

The maximum number of nodes in an 'm' ary tree with height h, where each node in the tree can have a maximum of m children is (m^(h+1) - 1) / (m - 1). 

Suppose m=2 i.e. a binary tree, then maximum number of nodes in a binary tree of height h is (2^(h+1) - 1) / (2 - 1) = 2^(h+1) - 1.


Note: m^h is "m to the power of h"  i.e 6^3=6 * 6* 6. 

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!!!

Read More