Binary Search Tree

Overview

You are given the classes BinaryTree1.java,, BinarySearchTree.java , and BinarySearchTreeTest.java .

Add the following member methods to the class BinarySearchTree :

depthOfMinValue Recursive () : returns the depth of the node in the calling BST which contains the minimum value. Use recursion.

depthOfMinValue Iterative ()):: returns the depth of the node in the calling BST which contains the minimum value. Do not use recursion.

equal Struct (BinarySearchTree bst2): Check if the calling BST and the bst2 have the same structure.

Test your methods in another class BinarySearchTree Test that uses the class BinarySearchTree and completes a number of operations on a single BinarySearchTree object and multiple BinarySearchTree objects.

implementation Requirements

You must use the classes provided to you.

This requirement means that you cannot use Java API class for Binary Search Tree.

You must implement the required methods as stated in the BinarySearchTree class.

---BinarySearchTree.java---

import java.util.List;

import java.util.ArrayList;

public class BinarySearchTree> extends BinaryTree1 implements SearchTree {

protected boolean addReturn; protected E deleteReturn; @Override public E find(E target) { return find(root, target); }

private E find(Node localRoot, E target) { if (localRoot == null) { return null; }

int compResult = target.compareTo(localRoot.data); if (compResult == 0) { return localRoot.data; } else if (compResult < 0) { return find(localRoot.left, target); } else { return find(localRoot.right, target); } } @Override public boolean add(E item) { root = add(root, item); return addReturn; }

private Node add(Node localRoot, E item) { if (localRoot == null) { // item is not in the tree insert it. addReturn = true; return new Node(item); } else if (item.compareTo(localRoot.data) == 0) { // item is equal to localRoot.data addReturn = false; return localRoot; } else if (item.compareTo(localRoot.data) < 0) { // item is less than localRoot.data localRoot.left = add(localRoot.left, item); return localRoot; } else { // item is greater than localRoot.data localRoot.right = add(localRoot.right, item); return localRoot; } } public E delete(E target) { root = delete(root, target); return deleteReturn; }

private Node delete(Node localRoot, E item) { if (localRoot == null) { // item is not in the tree. deleteReturn = null; return localRoot; }

// Search for item to delete. int compResult = item.compareTo(localRoot.data); if (compResult < 0) { // item is smaller than localRoot.data. localRoot.left = delete(localRoot.left, item); return localRoot; } else if (compResult > 0) { // item is larger than localRoot.data. localRoot.right = delete(localRoot.right, item); return localRoot; } else { // item is at local root. deleteReturn = localRoot.data; if (localRoot.left == null) { // If there is no left child, return right child // which can also be null. return localRoot.right; } else if (localRoot.right == null) { // If there is no right child, return left child. return localRoot.left; } else { // Node being deleted has 2 children, replace the data // with inorder predecessor. if (localRoot.left.right == null) { // The left child has no right child. // Replace the data with the data in the // left child. localRoot.data = localRoot.left.data; // Replace the left child with its left child. localRoot.left = localRoot.left.left; return localRoot; } else { // Search for the inorder predecessor (ip) and // replace deleted node's data with ip. localRoot.data = findLargestChild(localRoot.left); return localRoot; } } } } private E findLargestChild(Node parent) { // If the right child has no right child, it is // the inorder predecessor. if (parent.right.right == null) { E returnValue = parent.right.data; parent.right = parent.right.left; return returnValue; } else { return findLargestChild(parent.right); } } public boolean contains(E target) { return false; } public boolean remove(E target) { return false; }

}

---BinaryTree1---

import java.io.BufferedReader; import java.io.IOException; import java.io.Serializable; import java.util.Scanner;

public class BinaryTree1 implements Serializable {

protected static class Node implements Serializable {

public E data; public Node left; public Node right;

public Node(E data) { this.data = data; left = null; right = null; }

@Override public String toString() { return data.toString(); } } protected Node root;

public BinaryTree1() { root = null; }

protected BinaryTree1(Node root) { this.root = root; }

public BinaryTree1(E data, BinaryTree1 leftTree, BinaryTree1 rightTree) { root = new Node(data); if (leftTree != null) { root.left = leftTree.root; } else { root.left = null; } if (rightTree != null) { root.right = rightTree.root; } else { root.right = null; } }

public BinaryTree1 getLeftSubtree() { if (root != null && root.left != null) { return new BinaryTree1(root.left); } else { return null; } }

public BinaryTree1 getRightSubtree() { if (root != null && root.right != null) { return new BinaryTree1(root.right); } else { return null; } }

public E getData() { if (root != null) { return root.data; } else { return null; } }

public boolean isLeaf() { return (root == null || (root.left == null && root.right == null)); }

@Override public String toString() { StringBuilder sb = new StringBuilder(); preOrderTraverse(root, 1, sb); return sb.toString(); }

private void preOrderTraverse(Node node, int depth, StringBuilder sb) { for (int i = 1; i < depth; i++) { sb.append(" "); } if (node == null) { sb.append("null "); } else { sb.append(node.toString()); sb.append(" "); preOrderTraverse(node.left, depth + 1, sb); preOrderTraverse(node.right, depth + 1, sb); } }

public static BinaryTree1 readBinaryTree1(Scanner scan) { String data = scan.next(); if (data.equals("null")) { return null; } else { BinaryTree1 leftTree = readBinaryTree1(scan); BinaryTree1 rightTree = readBinaryTree1(scan); return new BinaryTree1(data, leftTree, rightTree); } }

}

---BinarySearchTreeTest---

public class BinarySearchTreeTest { public static void main(String[] args) { //create a binary search tree BinarySearchTree bstNames = new BinarySearchTree(); String[] names = {"house", "kiss", "dog", "cat", "man" }; System.out.println(bstNames.toString()); System.out.println("---------------------"); for (int i = 0; i < 5; i++) { bstNames.add(names[i]); System.out.println("After adding " + names[i] + "==> "); System.out.println(bstNames.toString()); System.out.println("---------------------"); } //verify the BST structure using inorder traversal System.out.println("**************"); System.out.println("Inorder traversal of names tree: "); //To be implemented by students in class BinarySearchTree //System.out.println(bstNames.inorderToString()); } }

---Search Tree---

public interface SearchTree> {

boolean add(E item);

boolean contains(E target);

E find(E target);

E delete(E target);

boolean remove(E target); }