CSC 310 Lab 1, Fall 2015

LEBANESE AMERICAN UNIVERSITY School of Arts and Science Department of Computer Science and Mathematics CSC 310: Algorithms and Data Structures Lab I 22. Jan. 2016 Implement the class BTNode which represents a binary tree node having an integer value and references to the left and right child. Using BTNode, implement the class BST representing a binary search tree that will be composed of multiple BTNodes. 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. Solve the following problems after finishing the BST insert implementation. Problem 1 Given a sequence of integers, insert them into a binary search tree then print the tree using pre- order traversal. Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be inserted into the tree. Output For each test case, print the tree using pre-order traversal. Sample Input Sample Output 7 25 13 10 30 15 27 37 4 6 7 8 9 6 10 7 15 13 4 6 25 12 10 15 30 27 37 6 7 8 9 10 7 4 6 15 13 Problem 2 Given a sequence of integers, insert them into a binary search tree then print the tree using in- order traversal. Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be inserted into the tree. Output For each test case, print the tree using in-order traversal. Sample Input Sample Output 7 25 13 10 30 15 27 37 4 6 7 8 9 6 10 7 15 13 4 6 10 13 15 25 27 30 37 6 7 8 9 4 6 7 10 13 15 Problem 3 Given a sequence of integers, insert them into a binary search tree then print the tree using post- order traversal. Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be inserted into the tree. Output For each test case, print the tree using post-order traversal. Sample Input Sample Output 7 25 13 10 30 15 27 37 10 15 13 27 37 30 25 9 8 7 6 4 6 7 8 9 6 10 7 15 13 4 6 6 4 7 13 15 10 Problem 4 Given a sequence of integers and a value k, insert them into a binary search tree then delete k from the tree. After deletion, print the tree using in-order traversal. Input Your program will be tested against multiple test cases. Each test case is made up of three lines. The first line contains an integer N representing the number of integers. The second line has N integers to be inserted into the tree. The third line contains an integer k representing the value to be deleted from the tree. Output For each test case, print the tree using in-order traversal after deletion of k. Sample Input Sample Output 7 25 13 10 30 15 27 37 10 4 6 7 8 9 9 6 10 7 15 13 4 6 4 25 12 15 30 27 37 6 7 8 10 7 6 15 13