Question

Q1: How many levels your binary search tree has (including level 0)? Is the binary search tree you created height balanced?

2.1 Click the animations “Binary Search Tree”. Click “Insert” button to insert
the following elements in the sequence, “50, 20, 30, 70, 90, 80, 40, 10, 5, 60,
85, 95”.

http://algoanim.ide.sk/index.php?page=showanim&id=44

Q2: What is the insertion process of the binary search tree? The new identical element is inserted as left or right child of the existing same value?

2.3 Fill another identical 65 in the blank of Insert, and click Insert to insert this
element.

Q3: What is the find process of the binary tree? If we have the multiple appearance of an element, such as 52, can both be found?

2.4 Fill 60 in the blank on the left of Find button, and click Find to search this
element, we have Figure 4 after it is found. Try again using some element is
not in the tree, such as 52 in my case.

Q4: What is traverse process and what is the visiting result? What order it is, prefix (Middle->Left->Right), postfix (Left->Right->Middle), or infix (Left->Middle->Right)?

2.5 Click print button to observe the traverse process.

Q5: What is delete process? Which element is selected to replace in the position of 70?

2.6 Click Del to delete 70, we will have Figure 5

      Q6: List all the major changes (such as color change, rotations) happening during the insertion process for each value?

3.1 Click the animations “Red/Black Tree”. Click “Insert” button to insert the
following elements in the sequence, “10, 20, 30, 40, 50, 60, 70, 80, 90”. The
created figure is Figure 6.

http://algoanim.ide.sk/index.php?page=showanim&id=63

Q7 : What is the find process of the red/black tree?

3.2 Fill 60 in the blank on the left of Find button, and click Find to search this
element

Answer 1

Q2. According to definition of Binary search tree (BST):- BST is a kind of binary tree in which right child should be greater than its parent and left child should be less than its parent.

Insertion Process:-

step 1: If you try to insert any new key value then first check it from root element of tree. If new key value is greater than root then go to right child of root and if less than root then go to left child.

according to above condition, you will reach to reach either left or right child of root(parent) node. if child is NULL then Insert the key value as new node i.e left or right child depends on above condition.

step 2: If child is not NULL then again compare to child node, if ne

w key value is greater then go to right child , key value is less then go to left child and if equal then display "Duplicate Value and finish them.

Step 3:; Repeat above step 1 and 2 for every new key value

according to above definition there is no any place of Identical ( means Duplicate elements) elements. Duplicate elements will discard with the message of "Duplicate Elements can't be insert".

Q2.3 according to list given in Q2.1 If Insert first key value as 65 then 65 will insert as right child of 60 and you insert again next key value is also 65 then this should be disacard as duplicate value in the tree according to definition of Binary search Tree.

please note if insertion of duplicate is necessity for searching and sorting operation then you can.can insert duplicate value as right child of parent.

Q3. If you would like to find any key value then first compare to Root Node (simply can say par in general)

Case 1: In normal course "Duplicate Entry is not permitted"  

initialise a pointer variable  p= root;  

while(P!=NULL)

{

if (key> p->val)

p=p->right;

else if(p->val==Key)

{

printf("\n Key value Found");

break;

}

else

p=p->left;

}

if (p==NULL)

Printf(" Key value not found");

Case 2: In normal course "Duplicate Entry is permitted" (as you required)

initialise a pointer variable  p= root;  

int flag==0;

while(P!=NULL)

{

if (key> p->val)

p=p->right;

else if(p->val==Key)

{

flag==1;

Printf(" Key value found");

}

else

p=p->left;

}

if (p==NULL && Flag==0)

Printf(" Key value not found");

In case 2 we can find both elements.

Q4. infix (Left->Middle->Right) we always find list in sorted order of list (Ascending)

according to given list in Q2.1 infix order or can say Inorder of Binary search tree is

(5,10,20,30,40,50,60,70,80,90)

postfix (Left->Right->Middle) or postorder

(5,10,40,30,20,60,80,90,70, 50)

prefix (Middle->Left->Right) or preorder

(50, 20, 10, 5, 30, 40, 70, 60, 90, 80)

No any specific ordering ( either Ascending and Descending) in case of prefix and postfix.

only Infix traversing is used  for sorting purpose.