Data structure (module 4)

MODULE IV
1. Define Binary search tree. Draw the BST for the following input:
14 15 4 9 7 18 3 5 16 20 17 9
Give the recursive search function to search an element in that tree (6)
2. Write c function to insert an element in a Binary Search Tree (4)
3. Write the recursive search and Iterative search algorithm for a binary search tree (8)
4. For the given data, draw a binary search tree and show the array and linked representation of the
same(6) 100, 85, 45, 55, 110, 20, 70, 65
5. Construct binary search tree for the given set of values 14, 15, 4, 9, 7, 18, 3, 5, 16, 20. Also perform
inorder, preorder, and postorder traversal of the obtained tree (6)
6. Construct a binary search tree by using the following in-order and post-order traversals (6)
a. In-order: BCAEDGHFI
b. Preorder: ABCDEFGHI
7. A binary tree has 9 nodes. The inorder and preorder traversals yield the following sequences of
nodes:
Inorder : E A C K F H D B G
Preorder : F A E K C D H G B
Draw a binary tree. Also perform the post-order traversal of the obtained tree(6)
8. Define the following terminologies with examples: (8)
a. Digraph
b. Weighted graph
c. Self-loop
d. Parallel edges
e. Multigraph
f. Complete Graph
9. Define graph. For the given graph show the adjacency matrix and adjacency list representation of
the graph (8)
10. Write an algorithm for Breadth first search and Depth first search (8)
11. What are the methods used for traversing a graph. Explain any one with example and write the C
function for the same (8)
12. Define selection tree. Construct min winner tree for the runs of a game given below. Each run
consists of values of players. Find the first 5 winners.
10 9 20 6 8 9 90 17
15 20 20 15 15 11 95 18
16 38 30 25 50 16 99 20
28

13. Define Forest. Transform the given forest into a Binary tree and traverse using inorder, preorder
and postorder traversal.

,1. Define Binary search tree. Draw the BST for the following input:
14 15 4 9 7 18 3 5 16 20 17 9
Give the recursive search function to search an element in that tree (6)

Definition: A binary search tree is a binary tree. It may be empty. If it is not empty, it satisfies the
following properties

• Every element has a key, and no two elements have the same key, that is, the keys are unique.
• The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.
• The keys in a nonempty right subtree must be larger than the key in the root of the subtree.
• The left and right subtrees are also binary search trees




• Recursive search

treepointer search(treepointer root, int key)
{
if (!root) return NULL;
if (key == root->data)
return root;
if (key < root->data)
return search(root->left_child, key);
return search(root->right_child,key);
}

2. Write function to insert an element in a Binary Search Tree(4)

, In a binary search tree, the insertion operation is performed with O(log n) time complexity. In
binary search tree, new node is always inserted as a leaf node. The insertion operation is performed
as follows...
Step 1: Create a newNode with given value and set its left and right to NULL
Step 2: Check whether tree is Empty
Step 3: If the tree is Empty, then set set root to newNode
Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or larger than the
node (here it is root node)
Step 5: If newNode is smaller than or equal to the node, then move to its left child. If newNode is
larger than the node, then move to its right child
Step 6: Repeat the above step until we reach a node (e.i., reach to NULL) where search terminates
Step 7: After reaching a last node, then insert the newNode as left child if newNode is smaller or
equal to that node else insert it as right child


C function to Insert an element in BST

Insert (TREE, VAL)
Step 1: IF TREE = NULL
Allocate memory for TREE
SET TREE DATA = VAL
SET TREE LEFT = TREE RIGHT = NULL
ELSE
IF VAL < TREE DATA
Insert(TREE LEFT, VAL)
ELSE
Insert(TREE RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: END


3. Write the recursive search and Iterative search algorithm for a binary search tree(8)

• To search for an element with a key, begin at the root.
• If the root is NULL, the search tree contains no elements and the search is unsuccessful.
• Otherwise, compare key with the key value in root. If key equals root's key value, then the search
terminates successfully. If key is less than roof s key value, then no element in the right subtree can
have a key value equal to key. Therefore, we search the left subtree of root. If key is larger than roofs
key value, we search the right subtree of root. The function search (Program 5.15) recursively searches
the subtrees.
• Recursive search

treepointer search(treepointer root, int key)
{
if (!root) return NULL;
if (key == root->data)
return root;
if (key < root->data)