Question

A binary search tree can be built with a traditional insertion method given a list of integers. Binary search trees (BSTs) are binary trees where the data is ordered such that nodes in the subtree to the left of a given node are smaller than or equal to the node, and the right subtree will contain nodes with values greater than the given node. With a built binary search tree, one can traverse the tree to print each node’s data in each order of traversal or perform some other operations. Further, one can tell by comparing nodes between two given trees whether they relate to each other, by having a reflected symmetric structure (i.e. being mirror images of each other), having identical structure, or not being related at all. In this assignment, you are asked to implement the following features.
Hard-code some paired lists of integers.
Build binary search trees from each list
Print the binary search trees in the three orders discussed in class.
Determine if the two binary search trees are identical, mirrors of each other, or neither
Remove a number in each tree at random and compare the tree pair again

Further, since the methods of the binary search tree class have been presented with recursive function calls, it is now up to you to implement these recursive functions with iterative loops.

You must write a Class Node, a class TreeChecker and a class BinarySearchTree. For Java users, they must implement the following interfaces respectively:

public interface INode {

   //Getter of node data
   T getData();

   //Setter of node data
   void setData(T data);

    INode getLeftChild() ;

   void setLeftChild(INode leftChild) ;

   INode getRightChild() ;

   void setRightChild(INode rightChild);
  
}
public interface ITree {
   void setRoot(INode root);
INode getRoot();
void preorder();   // print tree in a preorder traversal
void inorder();   // print tree in an inorder traversal
void postorder();   // print tree in a postorder traversal
INode insert(INode root, T data); // insert data into tree
   INode remove(INode root, T data); //search/remove node with data
   T search(INode root, T data); //search and return data if it exists
   INode getMax(INode root); //return node with maximum value of subtree
   INode getMin(INode root); //return node with minimum value of subtree
}  
public interface ITreeChecker {
  
boolean isMirror(ITree root1, ITree root2); // check if two trees are mirror
// images
   boolean isSame(ITree root1, ITree root2); // check if two trees are identical
}

Answer 1

P.S : No doubt its a huge code please check it attentively before dislike it. I don't need a thumbsup but I just want you to check it minutely.

I have provided the class as asked in the question with the implementation of the interfaces.

**I have considered the data as Integer for the sack of simplicity you may edit it as per requirement**

class Node implements INode
{
int data;
Node left, right;
  
public Node(int item)
{
data = item;
left = right = null;
}
public setData(int data)
{
this.data = data;
}
public int getData()
{
return data;
}
public setLeftChild(Node left)
{
this.left = left;
}
public setRightChild(Node Right)
{
this.right = right;
}
public getLeftChild()
{
return left;
}
public getRightChild()
{
return right;
}
  
}
class BinarySearchTree implements ITree
{
Node root;
void setRoot(Node node)
{
Node(node);
}
Node getRoot()
{
return root;
}
public void preorder()
{
iterativePreorder(root);
}
  
// An iterative process to print preorder traversal of Binary tree
void iterativePreorder(Node node)
{
  
// Base Case
if (node == null) {
return;
}
  
// Create an empty stack and push root to it
Stack<Node> ns = new Stack<Node>();
ns.push(root);
  
/* Pop all items one by one. Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first so that left is processed first */
while (ns.empty() == false) {
  
// Pop the top item from stack and print it
Node n = ns.peek();
System.out.print(n.data + " ");
ns.pop();
  
// Push right and left children of the popped node to stack
if (n.right != null) {
ns.push(n.right);
}
if (n.left != null) {
ns.push(n.left);
}
}
}
void inorder()
{
if (root == null)
return;
  
  
Stack<Node> ns = new Stack<Node>();
Node curr = root;
  
// traverse the tree
while (curr != null || ns.size() > 0)
{
  
/* Reach the left most Node of the
curr Node */
while (curr != null)
{
/* place pointer to a tree node on
the stack before traversing
the node's left subtree */
ns.push(curr);
curr = curr.left;
}
  
/* Current must be NULL at this point */
curr = ns.pop();
  
System.out.print(curr.data + " ");
  
/* we have visited the node and its
left subtree. Now, it's right
subtree's turn */
curr = curr.right;
}
}
ArrayList<Integer> res = new ArrayList<Integer>();
public void postorder()
{
res=postOrderIterative(root);
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
  
}
ArrayList<Integer> list = new ArrayList<Integer>();

// An iterative function to do postorder traversal
// of a given binary tree
ArrayList<Integer> postOrderIterative(Node node)
{
Stack<Node> S = new Stack<Node>();

// Check for empty tree
if (node == null)
return list;
S.push(node);
Node prev = null;
while (!S.isEmpty())
{
Node current = S.peek();

/* go down the tree in search of a leaf an if so process it
and pop stack otherwise move down */
if (prev == null || prev.left == current ||
prev.right == current)
{
if (current.left != null)
S.push(current.left);
else if (current.right != null)
S.push(current.right);
else
{
S.pop();
list.add(current.data);
}

/* go up the tree from left node, if the child is right
push it onto stack otherwise process parent and pop
stack */
}
else if (current.left == prev)
{
if (current.right != null)
S.push(current.right);
else
{
S.pop();
list.add(current.data);
}

/* go up the tree from right node and after coming back
from right node process parent and pop stack */
}
else if (current.right == prev)
{
S.pop();
list.add(current.data);
}

prev = current;
}

return list;
}
static Node newNode(int data)
{
Node temp = new Node();

temp.key = data;

temp.left = null;
temp.right = null;

return temp;
}
public Node insert(Node root, int key)
{
// Create a new Node containing
// the new element
Node newnode = newNode(key);

// Pointer to start traversing from root and
// traverses downward path to search
// where the new node to be inserted
Node x = root;

// Pointer y maintains the trailing
// pointer of x
Node y = null;

while (x != null) {
y = x;
if (key < x.key)
x = x.left;
else
x = x.right;
}

// If the root is null i.e the tree is empty
// The new node is the root node
if (y == null)
y = newnode;

// If the new key is less then the leaf node key
// Assign the new node to be its left child
else if (key < y.key)
y.left = newnode;

// else assign the new node its right child
else
y.right = newnode;

// Returns the pointer where the
// new node is inserted
return y;
}
public void remove(Node root,int value) {

if (root == null) {
System.out.println("There are no nodes in this Binary Search Tree");
}
else
{

Node currentNode = root;
Node parentNode = null;

while (true) {

if (value > currentNode.getData()) {

if (currentNode.getRightChild() != null) {

parentNode = currentNode;
currentNode = currentNode.getRightChild();
} else {

System.out.println("No Node is present with this value");
break;
}
} else if (value < currentNode.getData()) {

if (currentNode.getLeftChild() != null) {

parentNode = currentNode;
currentNode = currentNode.getLeftChild();
} else {

System.out.println("No Node is present with this value");
break;
}
} else {

if (currentNode.getLeftChild() == null
&& currentNode.getRightChild() == null) {
if (parentNode == null) {
rootNode = null;
} else if (parentNode.getLeftChild().getData() == currentNode.getData()) {

parentNode.setLeftChild(null);
} else {
parentNode.setRightChild(null);
}
} else if (currentNode.getLeftChild() == null) {
if (parentNode == null) {
root = currentNode.getRightChild();
} else if (parentNode.getLeftChild().getData() == currentNode.getData()) {

parentNode.setLeftChild(currentNode.getRightChild());
} else {
parentNode.setRightChild(currentNode.getRightChild());
}
} else if (currentNode.getRightChild() == null) {
if (parentNode == null) {
root = currentNode.getLeftChild();
} else if (parentNode.getLeftChild().getData() == currentNode.getData()) {

parentNode.setLeftChild(currentNode.getLeftChild());
} else {
parentNode.setRightChild(currentNode.getLeftChild());
}
} else {
int successorNodeValue = getSuccessorNodeValue(currentNode.getRightChild());
delete(successorNodeValue);
currentNode.setData(successorNodeValue);
}
}
}
}
}

private int getSuccessorNodeValue(Node currentNode) {

while (true) {
if (currentNode.getLeftChild() != null) {

currentNode = currentNode.getLeftChild();
} else {
break;
}
}

return currentNode.getData();
}
public int search(Node root, int key)
{
// Traverse untill root reaches to dead end
while (root != null) {
// pass right subtree as new tree
if (key > root.data)
root = root.right;
  
// pass left subtree as new tree
else if (key < root.data)
root = root.left;
else
return key; // if the key is found return it otherwise return -1
}
return -1;
}
public Node getMax(Node root)
{
Node current = root;
  
/* loop down to find the rightmost leaf */
while (current.right != null) {
current = current.right;
}
return (current);
  
}
public Node getMin(Node root) {
Node current = root;
  
/* loop down to find the leftmost leaf */
while (current.left != null) {
current = current.left;
}
return (current);
}
}
class TreeChecker implements ITreeChecker
{
public boolean isMirror(Node root1, Node root2) {
Stack<Node> st1 = new Stack<Node> ();
Stack<Node> st2 = new Stack<Node> ();
while (true)
{
// iterative inorder traversal of 1st tree and
// reverse inoder traversal of 2nd tree
while (root1 != null && root2 != null)
{
// if the corresponding nodes in the two traversal
// have different data values, then they are not
// mirrors of each other.
if (root1.data != root2.data)
return false;
  
st1.push(root1);
st2.push(root2);
root1 = root1.left;
root2 = root2.right;
}
  
// if at any point one root becomes null and
// the other root is not null, then they are
// not mirrors. This condition verifies that
// structures of tree are mirrors of each other.
if (!(root1 == null && root2 == null))
return false;
  
if (!st1.isEmpty() && !st2.isEmpty())
{
root1 = st1.peek();
root2 = st2.peek();
st1.pop();
st2.pop();
  
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
root1 = root1.right;
  
/* we have visited the node and its right subtree.
Now, it's left subtree's turn */
root2 = root2.left;
}
  
// both the trees have been completely traversed
else
break;
}
  
// tress are mirrors of each other
return true;
}
public boolean isSame(Node root1, Node root2)
{
// Return true if both trees are empty
if (root1 == null && root2 == null) return true;
  
// Return false if one is empty and other is not
if (root1 == null || root2 == null) return false;
  
// Create an empty queues for simultaneous traversals
Queue<Node > q1 = new LinkedList<Node> ();
Queue<Node> q2 = new LinkedList<Node> ();
  
// Enqueue Roots of trees in respective queues
q1.add(root1);
q2.add(root2);
  
while (!q1.isEmpty() && !q2.isEmpty())
{
// Get front nodes and compare them
Node n1 = q1.peek();
Node n2 = q2.peek();
  
if (n1.data != n2.data)
return false;
  
// Remove front nodes from queues
q1.remove();
q2.remove();
  
/* Enqueue left children of both nodes */
if (n1.left != null && n2.left != null)
{
q1.add(n1.left);
q2.add(n2.left);
}
  
// If one left child is empty and other is not
else if (n1.left != null || n2.left != null)
return false;
  
// Right child code (Similar to left child code)
if (n1.right != null && n2.right != null)
{
q1.add(n1.right);
q2.add(n2.right);
}
else if (n1.right != null || n2.right != null)
return false;
}
  
return true;
}

}