in JAVA Design and implement a method height for BinarySearchTree, that returns
ID: 3835011 • Letter: I
Question
in JAVA
Design and implement a method height for BinarySearchTree, that returns the height of the tree and
- uses recursion.
- does not use recursion.
//---------------------------------------------------------------------------
// BinarySearchTree.java by Dale/Joyce/Weems Chapter 7
//
// Defines all constructs for a reference-based BST.
// Supports three traversal orders Preorder, Postorder, & Inorder ("natural")
//---------------------------------------------------------------------------
//package ch07.trees;
import java.util.*; // Iterator, Comparator
//import ch04.queues.*;
//import ch02.stacks.*;
//import support.BSTNode;
public class BinarySearchTree<T> implements BSTInterface<T>
{
protected BSTNode<T> root; // reference to the root of this BST
protected Comparator<T> comp; // used for all comparisons
protected boolean found; // used by remove
public BinarySearchTree()
// Precondition: T implements Comparable
// Creates an empty BST object - uses the natural order of elements.
{
root = null;
comp = new Comparator<T>()
{
public int compare(T element1, T element2)
{
return ((Comparable)element1).compareTo(element2);
}
};
}
public BinarySearchTree(Comparator<T> comp)
// Creates an empty BST object - uses Comparator comp for order
// of elements.
{
root = null;
this.comp = comp;
}
public boolean isFull()
// Returns false; this link-based BST is never full.
{
return false;
}
public boolean isEmpty()
// Returns true if this BST is empty; otherwise, returns false.
{
return (root == null);
}
public T min()
// If this BST is empty, returns null;
// otherwise returns the smallest element of the tree.
{
if (isEmpty())
return null;
else
{
BSTNode<T> node = root;
while (node.getLeft() != null)
node = node.getLeft();
return node.getInfo();
}
}
public T max()
// If this BST is empty, returns null;
// otherwise returns the largest element of the tree.
{
if (isEmpty())
return null;
else
{
BSTNode<T> node = root;
while (node.getRight() != null)
node = node.getRight();
return node.getInfo();
}
}
public int size()
// Returns the number of elements in this BST.
{
int count = 0;
if (root != null)
{
LinkedStack<BSTNode<T>> nodeStack = new LinkedStack<BSTNode<T>>;
BSTNode<T> currNode;
nodeStack.push(root);
while (!nodeStack.isEmpty())
{
currNode = nodeStack.top();
nodeStack.pop();
count++;
if (currNode.getLeft() != null)
nodeStack.push(currNode.getLeft());
if (currNode.getRight() != null)
nodeStack.push(currNode.getRight());
}
}
return count;
}
}
//---------------------------------------------------------------------------
// BSTInterface.java by Dale/Joyce/Weems Chapter 7
//
// Interface for a class that implements a binary search tree (BST).
//
// The trees are unbounded and allow duplicate elements, but do not allow
// null elements. As a general precondition, null elements are not passed as
// arguments to any of the methods.
//---------------------------------------------------------------------------
//package ch07.trees;
//import ch05.collections.CollectionInterface;
import java.util.Iterator;
public interface BSTInterface<T> extends Iterable<T> //extends CollectionInterface<T>,
{
// Used to specify traversal order.
public enum Traversal {Inorder, Preorder, Postorder};
T min();
// If this BST is empty, returns null;
// otherwise returns the smallest element of the tree.
T max();
// If this BST is empty, returns null;
// otherwise returns the largest element of the tree.
public Iterator<T> getIterator(Traversal orderType);
// Creates and returns an Iterator providing a traversal of a "snapshot"
// of the current tree in the order indicated by the argument.
int size();
// Returns the number of elements in this collection.
}
//---------------------------------------------------------------------------
// BSTNode.java by Dale/Joyce/Weems Chapter 7
//
// Implements nodes holding info of class <T> for a binary search tree.
//---------------------------------------------------------------------------
//package support;
public class BSTNode<T>
{
private T info; // The node info
private BSTNode<T> left; // A link to the left child node
private BSTNode<T> right; // A link to the right child node
public BSTNode(T info)
{
this.info = info; left = null; right = null;
}
public void setInfo(T info){this.info = info;}
public T getInfo(){return info;}
public void setLeft(BSTNode<T> link){left = link;}
public void setRight(BSTNode<T> link){right = link;}
public BSTNode<T> getLeft(){return left;}
public BSTNode<T> getRight(){return right;}
}
Explanation / Answer
int heightItrative()
{
if (root == null)
return 0;
// Create an empty queue for level order tarversal
Queue<BSTNode> q = new LinkedList();
// Enqueue Root and initialize height
q.add(root);
int height = 0;
while (true)
{
int nodeCount = q.size();
if (nodeCount == 0)
return height;
height++;
while (nodeCount > 0)
{
BSTNode newnode = q.peek();
q.remove();
if (newnode.getLeft() != null)
q.add(newnode.getLeft());
if (newnode.getRight() != null)
q.add(newnode.getRight());
nodeCount--;
}
}
}
int heightRec()
{
return heightRecHelper(root);
}
int heightRecHelper(BSTNode node)
{
if (node == null)
return 0;
int lDepth = heightRecHelper(node.getLeft());
int rDepth = heightRecHelper(node.getRight());
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.