Lab6

Problem:

[Cracking an adversary’s signal]

There is an adversary who has structured his confidential information as a binary tree. He has also encoded his information in prefix (obtained by the preorder traversal of the tree) and infix (obtained by the inorder traversal of the tree) forms. You somehow encounter some of his transmitted signals which are in terms of the prefix and infix representations. Your job is to decode the signals into their original binary tree forms.

Essentially, the problem can be stated as follows: Given an inorder traversal sequence and a preorder traversal sequence, construct the binary tree. The function to print the resultant tree in the dotty format is already given. So, you can visualize the generated tree using dotty application on Unix or using online dotty viewer.

Bonus:

Check and report a warning if the resultant binary tree violates the binary search tree property.

Starter files:

Copy the starter files from here:

/comp/15/public_html/labs/lab6/problem/

Sample inputs/outputs:

(1) Input from a file:

Input file1: inp1.txt

Run: ./bst < inp1.txt

OR, Input from the command line:

Output file name: out1.dot
Enter the number of nodes: 3
Enter the preorder sequence:
preorder[0] = 5
preorder[1] = 2
preorder[2] = 10
Enter the inorder sequence:
inorder[0] = 2
inorder[1] = 5
inorder[2] = 10

Expected Generated Output file: exp_out1.dot

(2) Input from a file:

Input file1: inp2.txt

Run: ./bst < inp2.txt

OR, Input from the command line:

Output file name: out2.dot
Enter the number of nodes: 4
Enter the preorder sequence:
preorder[0] = 6
preorder[1] = 2
preorder[2] = 10
preorder[3] = 8
Enter the inorder sequence:
inorder[0] = 2
inorder[1] = 6
inorder[2] = 8
inorder[3] = 10

Expected Generated Output fileexp_out2.dot

(3) Input from a file:

Input file1: inp3.txt

Run: ./bst < inp3.txt

OR, Input from the command line:

Output file name: out3.dot

Enter the number of nodes: 9
Enter the preorder sequence:
preorder[0] = 15
preorder[1] = 8
preorder[2] = 2
preorder[3] = 12
preorder[4] = 10
preorder[5] = 14
preorder[6] = 50
preorder[7] = 25
preorder[8] = 75
Enter the inorder sequence:
inorder[0] = 2
inorder[1] = 8
inorder[2] = 10
inorder[3] = 12
inorder[4] = 14
inorder[5] = 15
inorder[6] = 25
inorder[7] = 50
inorder[8] = 75

Expected Generated Output fileexp_out3.dot

(4) Input from a file:

Input file1: inp1e.txt

Run: ./bst < inp1e.txt

OR, Input from the command line:

Output file name: out1e.dot
Enter the number of nodes: 3
Enter the preorder sequence:
preorder[0] = 6
preorder[1] = 2
preorder[2] = 10
Enter the inorder sequence:
inorder[0] = 2
inorder[1] = 5
inorder[2] = 10

Expected Output:

Error: Illegal entry found in the inorder sequence.

(5) Input from a file:

Input file1: inp2e.txt

Run: ./bst < inp2e.txt

OR, Input from the command line:

Output file name: out2.dot
Enter the number of nodes: 4
Enter the preorder sequence:
preorder[0] = 6
preorder[1] = 2
preorder[2] = 10
preorder[3] = 8
Enter the inorder sequence:
inorder[0] = 2
inorder[1] = 10
inorder[2] = 8
inorder[3] = 6

Expected output (if attempting the bonus question):

Warning: BST property violation.

Expected Generated Output file: exp_out2e.dot