Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

I need help with the addHelper method towards the botto of this code.. thanks package apps; public class MyBST { BSTNode root; public MyBST() {

I need help with the addHelper method towards the botto of this code.. thanks

package apps;

public class MyBST {

BSTNode root;

public MyBST() {

root = null;

}

public void printBST() {

inOrder(root);

//showBST(root, "");

System.out.println();

}

private void showBST(BSTNodenode, String indent) {

if (node == null) return;

System.out.println(indent+node.info);

showBST(node.left, indent+" ");

showBST(node.right, indent+" ");

}

private void preOrder(BSTNode node) {

if (node == null) return;

System.out.print(node.info + " ");

preOrder(node.left);

preOrder(node.right);

}

private void inOrder(BSTNode node) {

if (node == null) return;

inOrder(node.left);

System.out.print(node.info + " ");

inOrder(node.right);

}

public T min() {

if (root == null) return null;

BSTNode node = root;

while( node.left != null)

node = node.left;

return node.info;

}

public T max() {

// returns the maximum value. This is complete.

return maxHelper(root);

}

public T maxHelper(BSTNode node) {

// Use recursion.

// Need work here

if(root.right == null) {

return root.info;

}

else {

return maxHelper(root.right);

}

}

public int height(){

// returns the height of the tree. This is complete

return heightHelper(root);

}

public int heightHelper(BSTNode node) {

// Use recursion.

// Need work here

}

public int size() {

// returns the number of nodes in the binary search tree

if (root.left == null && root.right == null) {

return 1;

}

else {

int count = 0;

if (root.left != null) {

count += root.left.size();

}

if (root.right != null) {

count += root.right.size();

}

return count;

}

}

public BSTNode search(T val){

// returns the node that has the same value to the given input

// Just depend on searchHelper. This is complete

return searchHelper(root, val);

}

public BSTNode searchHelper(BSTNode node, T val){

// search from the given node

// Use recursion

// Need work

// if val is equal to node.info, then return the node.

// if val is smaller than node.info, then return searchHelper(node.left, val)

// if val is larger than node.info, then return searchHelper(node.right, val)

}

public void add(T val){

// Just depend on addHelper. This is complete

root = addHelper(root, val);

}

public BSTNode addHelper(BSTNode node, T val){

// Use recursion.

// Need work

// This functions returns a node (either current one or new node)

// and its parent will make connection to the node this returns.

// if val is smaller than or equal to node.info, then node.left = addHelper(node.left, val)

// if( val < node.info )

if (node == null) {

// create a new node with val

// return that node;

}

if( ((Comparable) val).compareTo(node.info) < 0) {

node.left = addHelper(node.left, val);

return node;

}

// if val is larger than node.info, then node.right = addHelper(node.right, val)

}

public void remove(T val) {

root = removeHelper(root, val);

}

public BSTNode removeHelper(BSTNode node, T val) {

if( ((Comparable)val).compareTo(node.info)<0 ) {

node.left = removeHelper(node.left, val);

return node;

}

else if ( ((Comparable)val).compareTo(node.info) > 0 ) {

node.right = removeHelper(node.right, val);

return node;

}

else { // val == node.info

if (node.left==null && node.right==null)

return null;

else if (node.left == null)

return node.right;

else if (node.right == null)

return node.left;

else {

T predecessor = maxHelper(node.left);

node.info = predecessor;

removeHelper(node.left, predecessor);

return node;

}

}

}

}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Professional Microsoft SQL Server 2012 Administration

Authors: Adam Jorgensen, Steven Wort

1st Edition

1118106881, 9781118106884

More Books

Students also viewed these Databases questions

Question

Provide examples of Dimensional Tables.

Answered: 1 week ago