/ Binary search tree node

class Node {

private int info; //element stored in this node

private Node left; //link to left child

private Node right; //link to right child

// Initializes the node

Node() {

info = 0;

left = right = null;

}

// Sets this node

void setNode(int x, Node l, Node r) {

info = x;

left = l;

right = r;

}

// Returns the value in this node

int getInfo() {

return info;

}

// Returns the link to the left child

Node getLeftChild() {

return left;

}

// Returns the link to the right child

Node getRightChild() {

return right;

}

// Sets the value for this node

void setInfo(int x) {

info = x;

}

// Sets the link to the left child

void setLeftChild(Node l) {

left = l;

}

// Sets the link to the right child

void setRightChild(Node r) {

right = r;

}

}

///////////////////////////////////////////////////////////////////////////////

// Class implementing a binary search tree

class BinarySearchTree {

private Node root; //root of the bst. It's implemented as a dummy node.

// Initializes the bst to empty creating a dummy root node

public BinarySearchTree() {

root = new Node(); //dummy node as the root

root.setLeftChild(null);

root.setRightChild(null);

root.setInfo(-1);

}

// Determines whether the bst is empty

public boolean isEmpty() {

return root.getLeftChild() == null;

}

// Prints the bst elements using inorder traversal

// This method invokes the private inorderDisplay mehod

public void display() {

inorderDisplay(root.getLeftChild());

System.out.println();

}

// Determines if an item exists in the bst. This method invokes the private

// method search, passing to it the element to be found and the root

// of the actual tree.

public boolean contains(int x) {

return search(x, root.getLeftChild());

}

// Adds the element x to the bst. This method invokes the private method

// insert, passing to it the element to be added to the bst and the root

// of the actual tree.

public void add(int x) {

if (root.getLeftChild() == null) {

Node p = new Node();

p.setNode(x, null, null);

root.setLeftChild(p);

} else

insert(x, root.getLeftChild());

}

// Finds the smallest element in the bst. This method invokes the overloaded

// method getMin, passing to it the root of the tree.

public int getMin() {

return getMin(root);

}

////////////////// Private methods ////////////////////////////////////////

// Prints the elements of the subtree whose root is referenced by p. Uses

// inorder traversal.

private void inorderDisplay(Node p) {

if (p != null) {

inorderDisplay(p.getLeftChild());

System.out.print(p.getInfo() + " ");

inorderDisplay(p.getRightChild());

}

}

// Finds if x is inserted in the subtree whose root is referenced by p. The

// search is conducted recursively, using the bst property: keys in the left

// subtree of a node are smaller than or equal to the key in the node, while

// the keys in the right subtree of the node are greater.

private boolean search(int x, Node p) {

if (p == null)

return false;

else if (x == p.getInfo())

return true;

else if (x < p.getInfo())

return search(x, p.getLeftChild());

else

return search(x, p.getRightChild());

}

// Adds x to the subtree referenced by p. The search for the location to

// insert the new node is conducted recursively, using the bst property:

// keys in the left subtree of a node are smaller than or equal to the key

// in the node, while the keys in the right subtree of the node are greater.

private void insert(int x, Node p) {

if (x < p.getInfo())

if (p.getLeftChild() == null) {

Node q = new Node();

q.setNode(x, null, null);

p.setLeftChild(q);

}

else

insert(x, p.getLeftChild());

else if (p.getRightChild() == null) {

Node q = new Node();

q.setNode(x, null, null);

p.setRightChild(q);

}

else

insert(x, p.getRightChild());

}

// Recursively finds the smallest element in the subtree referenced by p.

// The method uses this property of BSTs: the smallest value is stored in

// the leftmost node.

private int getMin(Node p) {

if (p.getLeftChild() == null)

return p.getInfo();

else

return getMin(p.getLeftChild());

}

}

///////////////////////////////////////////////////////////////////////////////

// Class testing the binary search tree.

public class Lab6A {

public static void main(String[] args) {

BinarySearchTree bst = new BinarySearchTree();

for (int i = 0; i < 10; i++) {

int x = (int) (Math.random() * 100);

System.out.print(x + " ");

bst.add(x);

}

System.out.println();

bst.display();

}

}

Add a recursive function getHeight to the BinarySearchTree class in Exercise 1 that returns the height of the tree. Create a Main class to test it. Continue to display list of values added to tree and the sorted list resulting from display(), as in Exercise 1, followed by a print-out of the tree height. Repeat for several trees of different numbers of nodes.

PLEASE INCLUDE OUTPUT SCREENSHOT