Trees sure are neat. Let’s take this slow and simple and make a tree of integers.
Create a class IntBSTree with the following
Internal class Node Instance variables data: an integer value leftChild: a Node representing the child to the left rightChild: a Node representing the child to the right Instance variables root: a Node representing the first element in the tree. Methods insert: This method returns nothing and takes in an integer value that is then placed as a new node in the tree based on the binary tree properties. A reminder values greater than the parent go to the right subtree and values smaller go to the left subtree. Also it may be a good idea to use a recursive method in order to place these values. remove: This method returns nothing and takes in an integer value that is to be removed. First the method must search for the value. If the value is found the it is removed while preserving the integrity of the binary search tree. Remember there are cases for the node having no children, having one child, and having two children. printPreorder: This method which returns nothing and has no parameters prints the pre-order traversal of the tree. For pre-order traversal each the value is printed out, then left subtree must be visited, and finally each of the right subtrees is visited. It is a good idea to make a recursive method to assist with this. getDepth: The depth of a node is the number of edges from the root to that number. This method returns nothing and takes in a parameter corresponding to the integer value of a node whose depth is returned. If the value is not in the tree a -1 should be returned. Again a recursive helper method may be useful to solve this.
Create another file that creates an instance of the IntBSTree and tests each of the methods.