CS2094D-ASSIGNMENT 1 Solved

QUESTIONS
 

1.    A Binary Tree is a rooted tree in which each node is an object that contains a key value. In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate attribute contains the value NIL. The root node is the only node in the tree whose parent is NIL. The Parenthesis Representation of a binary tree is recursively defined as given below:

•   The string ( ) represents an empty tree.

•   The string ( k left-subtree right-subtree ) represents a tree whose root node has key k, leftsubtree is the left subtree of the root node in Parenthesis Representation and rightsubtree is the right subtree of the root node in Parenthesis Representation.

Write a program to create a binary tree T and print T in Parenthesis Representation. Your program should contain the following functions:

•   Insert(T,k) - inserts the element k to the tree T.

Note: To insert an element k into a binary tree T, do a level order traversal of the given tree T. If we find a node whose left child is empty, make new key k as left child of the node. Else if we find a node whose right child is empty, make the new key k as right child. i.e., keep traversing the tree until we find a node whose either left or right child is empty.

•   Print(T) - that should take as input a pointer to the root node of a binary tree and print the tree in its Parenthesis Representation.

Input format:

•   Each line contains a character from ‘i’, ‘p’and ‘e’ followed by at most one integer. The integers, if given, are in the range [−106,106].

•   Character ‘i’ is followed by an integer separated by single space. In this operation, a node with this integer as key is created and inserted into T.

•   Character ‘p’ is to print the Parenthesis Representation of the tree T.

•   Character ‘e’ is to ‘exit’ from the program.

Output Format:

•   The output is the space separated Parenthesis Representation of the tree T.

Sample Input:

i 4 i 3 i 9 i 5 i 6 i 1 i 8 p e

Sample Output:

( 4 ( 3 ( 5 ( ) ( ) ) ( 6 ( ) ( ) ) ) ( 9 ( 1 ( ) ( ) ) ( 8 ( ) ( ) ) ) )

2.    The Binary Search Tree (BST) data structure supports many of the dynamic-set operations. A BST is organized as a binary tree in which each node is an object that contains a key value. In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate attribute contains the value NIL. The root node is the only node in the tree whose parent is NIL. The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property:

•   Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key ≤

x.key. If y is a node in the right subtree of x, then y.key ≥ x.key.

Write a program to create a Binary Search Tree T and perform the operations insertion, deletion, search, find level, find minimum, find maximum, predecessor, successor and traversals(inorder, preorder and postorder) on T. Input should be read from console and output should be shown in console. Your program should include the following functions:

•   Main() - creates the Binary Search Tree T with T as the root node (which is NIL initially) and repeatedly reads a character ‘a’, ‘d’, ‘s’, ‘l’, ‘m’, ‘x’, ‘r’, ‘u’, ‘i’, ‘p’ or ‘t’ from the console and calls the sub-functions appropriately until character ‘e’ is entered for exiting the program.

•   CreateNode(k) creates a new node with key value k and returns a pointer to the new node. All the pointer attributes of the new node are set to NIL.

•   Insert(T,x) - inserts the node x into the BST T.

Note: The caller of this function is assumed to create the node x using the CreateNode function.

•   Delete(T,x) - deletes the node x from the BST T.

Note: The caller of this function is assumed to invoke Search function to locate the node x.

•   Search(T,k) - searches for a node with key k in T, and returns a pointer to a node with key k if one exists; otherwise, it returns NIL.

•   Level(T,k) - searches for a node with key k in T, and returns the level of the node with key k if one exists; otherwise, it returns NIL.

•   MinValue(T) returns the minimum value in the BST T.

•   MaxValue(T) returns the maximum value in the BST T.

•   Predecessor(T,y) - searches for a node with key y in T, and returns a pointer to a node which is predecessor of the node with key y if one exists; otherwise, it returns NIL.

•   Successor(T,y) - searches for a node with key y in T, and returns a pointer to a node which is successor of the node with key y if one exists; otherwise, it returns NIL.

•   Inorder(T) - performs recursive inorder traversal of the BST T and prints the key in the nodes of T in inorder.

•   Preorder(T) performs recursive preorder traversal of the BST T and prints the key in the nodes of T in preorder.

•   Postorder(T) performs recursive postorder traversal of the BST T and prints the key in the nodes of T in postorder.

Input format:

•   Each line contains a character from ‘a’, ‘d’, ‘s’, ‘l’, ‘m’, ‘x’, ‘r’, ‘u’, ‘i’, ‘p’, ‘t’ or ‘e’ followed by at most one integer. The integers, if given, are in the range [−106,106].

•   Character ‘a’ is followed by an integer separated by single space. In this operation, a node with this integer as key is created and inserted into T.

•   Character ‘d’ is followed by an integer separated by single space. In this operation, the node with this integer as key is deleted from T and the deleted node’s key is printed.

•   Character ‘s’ is followed by an integer separated by single space. This operation is to find the node with this integer as key in T.

•   Character ‘l’ is followed by an integer separated by single space. This operation is to find the level of the node with this integer as key in T.

•   Character ‘m’ is to find the minimum value of T.

•   Character ‘x’ is to find the maximum value of T.

•   Character ‘r’ is followed by an integer separated by single space. This operation is to find the predecessor of the node with this integer as key in T.

•   Character ‘u’ is followed by an integer separated by single space. This operation is to find the successor of the node with this integer as key in T.

•   Character ‘i’ is to perform inorder traversal of T.

•   Character ‘p’ is to perform preorder traversal of T.

•   Character ‘t’ is to perform postorder traversal of T.

•   Character ‘e’ is to ‘exit’ from the program.

Output Format:

•   The output (if any) of each command should be printed on a separate line.

•   For option ‘d’, print the deleted node’s key. If a node with the input key is not present in T, then print -1.

•   For option ‘s’, if the key is present in T, then print 1. If key is not present in T, then print -1.

•   For option ‘l’, if the key is present in T, then print its level. If key is not present in T, then print -1.

•   For option ‘m’, print the minimum value of T.

•   For option ‘x’, print the maximum value of T.

•   For option ‘r’, if the key is present in T, then print its predecessor. If key is not present in T, then print -1.

•   For option ‘u’, if the key is present in T, then print its successor. If key is not present in T, then print -1.

•   For option ‘i’, print the key in the nodes of T obtained from inorder traversal.

•   For option ‘p’, print the key in the nodes of T obtained from preorder traversal.

•   For option ‘t’, print the key in the nodes of T obtained from postorder traversal.

Sample Input:

a 25 a 13 a 50 a 45 a 55 a 18 l 50 l 19

m x r 25 u 30 u 25

i

p

t

s 10 s 25 d 55 d 13 d 10 d 25

i

s 25

e

Sample Output:

2

-1

13

55

18

-1

45

13 18 25 45 50 55

25 13 18 50 45 55

18 13 45 55 50 25

-1

1

55

13

-1

25

18 45 50

-1

3.    Given the Parenthesis Representation of a binary tree B, find the minimum number of proper subtrees of B that are to be deleted from B to convert it into a Binary Search Tree. A proper subtree of a tree T is a tree consisting of a node N (different from the root) and all descendants of N in T. In particular, a leaf node in T is a subtree of T. Note that in a single proper subtree deletion operation, all the nodes in that subtree are deleted.

Input format:

•   The first and only line of input contains the Parenthesis Representation of the given binary tree.

Output format:

•   A single line containing the minimum number of proper subtrees to be deleted from the given binary tree to convert it into a BST.

Sample Input 1:

( 15 ( 12 ( 32 ( 10 ( ) ( ) ) ( 35 ( ) ( ) ) ) ( 45 ( 41 ( ) ( ) ) ( 60 ( ) ( ) ) ) ) ( 30 ( ) ( 46 ( ) ( 50 ( ) ( ) ) ) ) )

Sample Output 1:

1

Sample Input 2: ( 10 ( 21 ( ) ( ) ) ( 9 ( ) ( ) ) )

Sample Output 2:

2

4.    Given the Parenthesis Representation of a binary tree T. Write a program to find the lowest common ancestor of two nodes in a given binary tree. Lowest Common Ancestor(LCA) of two nodes u and v in a tree is the shared ancestor of u and v that is located farthest from the root.

Input format:

•   The integers, if given, are in the range [−106,106].

•   First line of the input contains space separated Parenthesis Representation of the tree

T.

•   Second line contains two integers separated by a space, represents the value of u and v respectively.

Output format:

•   The output consist of a single integer value LCA.

Sample Input 1:

( 1 ( 2 ( 4 ( 8 ( ) ( ) ) ( 9 ( ) ( ) ) ) ( 5 ( ) ( ) ) ) ( 3 ( 6 ( 10 ( ) ( ) ) ( ) ) ( ) ) ) 5 9

Sample Output 1:

2

Sample Input 2:

( 1 ( 2 ( 4 ( 8 ( ) ( ) ) ( 9 ( ) ( ) ) ) ( 5 ( ) ( ) ) ) ( 3 ( 6 ( 10 ( ) ( ) ) ( ) ) ( ) ) ) 6 3

Sample Output 2:

3

5.    A sub-tree of a tree T is a tree S consisting of a node in T and all of its descendants in T. Given a Binary Tree T, write a program to find the size of the largest sub-tree which is a BST where size of the BST is the number of nodes present in it.

Input format:

•   The integers, if given, are in the range [−106,106].

•   Input contains space separated Parenthesis Representation of the tree T.

Output format:

•   Single line representing size of the largest BST.

Sample Input 1:

( 10 ( 15 ( 12 ( ) ( ) ) ( 20 ( ) ( ) ) ) ( 8 ( 5 ( ) ( ) ) ( 2 ( ) ( ) ) ) )

Sample Output 1:

3

Sample Input 2:

( 10 ( 16 ( 7 ( ) ( ) ) ( 24 ( 19 ( ) ( ) ) ( 29 ( ) ( ) ) ) ) ( 5 ( ) ( ) ) )

Sample Output 2:

5