CSC 310 Lab CSC310, Spring 2018

LEBANESE AMERICAN UNIVERSITY Department of Computer Science and Mathematics CSC 310: Algorithms and Data Structures Lab I Implement the class BTNode which represents a binary tree node having an integer value and references to the left child and right child, as well as a constructor that takes an integer as argument. Using BTNode, implement the class BST representing a binary search tree. In the BST class, implement the insert method, which takes as input an integer value and adds it to the tree maintaining the binary search tree structure. Problem 1 Given a sequence of integers, insert them into a binary search tree then print the tree using BFS. Each test case is made up of an integer N representing the number of nodes in the tree followed by N integers representing the values to insert. Sample Input Sample Output 7 25 13 10 30 15 27 37 25 13 10 15 30 27 37 4 6 7 8 9 7 6 8 9 6 10 7 15 13 4 6 10 6 4 7 15 13 Problem 2 Given a sequence of integers, insert them into a binary search tree then traverse the tree and print it using In-Order , Post-Order and Pre-Order traversals consecutively. The input is read from a file named “problem2.in”. The first line of input is an integer T representing the number of test cases. Each test case is made up of an integer N representing the number of nodes in the tree followed by N integers representing the values to insert. Sample Input Sample Output 1 3 5 6 1 2 4 7 1 2 3 4 5 6 7 2 1 4 7 6 5 3 3 1 2 5 4 6 7 Problem 3 Given a sequence of integers, insert them into a binary search tree then compute the height of the tree and print it. Each test case is made up of an integer N representing the number of nodes in the tree followed by N integers representing the values to insert. Sample Input Sample Output 7 3 1 5 2 4 6 7 3 Problem 4 Given a sequence of integers, insert them into a BST and then check if it is an AVL Tree. The first line of input is an integer N representing the number of nodes and it will be followed by N numbers that will be filled in the Tree. Sample Input Sample Output 6 20 25 40 10 30 50 not AVL 4 19 15 23 20 AVL Problem 5 Given a sequence of integers, insert them into a BST tree and then output the number of nodes followed by the number of leaves of that tree. The first line of input is an integer N representing the number of nodes and it will be followed by N numbers that will be filled in the Tree. Sample Input Sample Output 7 3 1 5 2 4 6 7 7 4 Problem 6 Write a program that reads a sequence of integers and sorts them using Insertion Sort. Sample Input Sample Output 7 12 700 9 156 34 -732 237 -732 9 12 34 156 237 700