CS515-MidSem Solved

Task 1: Creating the tree from the input data file
A binary search tree (BST) is to be constructed from the input (ip.txt) data file. Read the file, and create the BST using a pointer-based repreentation. Maintain links for left and right chlidren. The nodes of the tree are specified in level wise manner. Thus, root node and its children are mentioned first. In the subsequent lines, the child nodes are specified in left to right manner. All the key value of the node are unique and positive in nature. For each node, its key and the corresponding left and right child key values are provided. If left or right child is not available then it will be marked by

-1.

After creating the tree, it is required to return the pointer to the root node. In all of the subsequent parts, this pointer should be passed as the tree, not the raw data from the file.

Let’s consider the contents of the sample input file is as below.

Filename: ip.txt

48 38 60

38 31 -1

60 56 -1

31 15 34

56 -1 -1

15 -1 25

34 -1 -1

25 -1 -1

The BST corresponding to this input file is as given below

 

After constructing the tree from the given input, check whether it is a valid BST or not. Also, print the preorder and inorder traversal of the constructed tree. In this case,

the preorder traversal of the tree is 48 38 31 15 25 34 60 56 the inorder traversal of the tree is 15 25 31 34 38 48 56 60


Task 2: Finding the farthest leaf node(s) of the tree
In this task, you need to find the farthest leaf node(s) from the root in terms of number edges required to reach from the root to the leaf node.

For the aforementioned example, the farthest leaf node(s): 25

The distance of the leaf from the root is: 4


Task 3: Finding the tree after performing right rotation
Use the right rotation as shown in the following figure to perform rotation w.r.t. a node. Each rotation changes the root of the subtree at the position of rotation (the root changes from u to v for right rotation, according to the figure).

 

For performing the right rotation, we need to enter key value of the node. If right rotation can be performed then it performs the right rotation without violating BST property and prints the preorder and inorder traversal of the tree.

For the aforementioned example,

Enter key value for right rotation: 15

Right rotation w.r.t 15 is not possible

Enter key value for right rotation: 31

Right rotation w.r.t 31 is possible The tree after right rotation

 

the preorder traversal of the tree is 48 38 15 31 25 34 60 56 the inorder traversal of the tree is 15 25 31 34 38 48 56 60