CSC 16 Lab 11: Binary Trees and Search Trees Due next Tuesday A binary search tree is a special kind of binary tree that has the following recursive property: Every element in the left subtree of a node is less than or equal to the head of the node, and every element in the right subtree is greater than the head of the node. by "recursive" property I mean that this property must hold for ALL nodes (not just the root node). For example, the following is a valid binary search tree: 8 / \ 5 9 / \ \ 3 6 10 \ 7 But the following one is not: 8 / \ 5 9 / \ \ 3 6 10 \ 4 Although the property holds for the root, it fails to hold for all nodes (node 6). The following is also not a binary search tree: 8 / \ 5 9 / \ \ 3 11 10 This time, although the property appears to hold locally for every interior node, it's not true that ALL numbers on the left subtree of a node is <= the number at that node. Namely, The 11 can't be on the left subtree of 8. Following the code of trees I've given you (but write your own program!) you are asked to practice writing some basic operations on binary trees and search trees. Please understand clearly for every problem whether it's for a general binary tree or a binary search tree. The algorithm could be very different. For example, to find the smallest number on a binary SEARCH, you can just follow the .left pointer as far as possible. However, for general trees you have to recursively traverse the entire tree. the first 3 problems are for any tree: 0. Write a procedure public static void printtree(node T, String order) That prints out the nodes in the tree. The order argument is a string that's either "in", "pre" or "post", indicating the order the nodes should be printed. If order is any other string, default to inorder. Which order do you think should be used on binary search trees? WATCH OUT: to compare strings a, b in java, use a.equals(b). 1. An element can occur multiple times in a tree. Write a procedure similar to the "member" function, but which, instead of a boolean, returns the number of times that a number appears in a tree. public static int occurrences(int x, node T) 2. Write a procedure public static node copytree(node T) That creates an identical copy of the tree T, node for node. You can't just do { return T; } because that'll just return a pointer to the same structure. You need to create a completely new set of nodes. 3. The smallest number in a binary search tree is the left most element of the tree (follow the left pointers as far as possible). Similarly, the largest element can be found by following the right pointers as far as possible. Write functions that return the smallest and largest numbers in a binary search tree. 4. Modify the procedure for problem 1 above to work with a search tree. That is, it still needs to count the number of times an element occurs, but it should not have to look at the entire tree. Also, DO NOT use recursion. Hint: consider the following tree: 5 / \ 3 11 \ 5 If there's more than one occurence of a number (e.g. 5), it must be on the left subtree of that number. 5. Write a oop-style function public int depth() that computes the maximum depth (or height) of a tree. The max depth is the length of the longest branch of the tree. A singleton-node tree has depth one. Hint: the depth depends on the depths of the left subtree and right subtree. Note that whether the tree is a search tree makes no difference for this problem. 6. Modify the "insert" (for search tree) procedure I wrote (in node.java on homepage) to use recursion. Here's a recursive version of the "search" procedure public static node search(int x, node T) { if (T==null) return null; if (T.head==x) return T; if (x