Rubric

$90$points$-$ please implement and complete the six functions. points $-6$ functions implemented and stored as a separate commit

on GitHub

$10$ points $-$ Javadoc comments

Description

This assignment will get you familiar with the basic commands of Git, a

version control system. You will need to download Git $($see Version

Control.pptx for details$)$ and install it on your machine. There are a few

simple commands that you need to learn to be able to use Git. The basic

operations can be found in the power slides.

You will implement a few simple operations for a Binary Search Tree.

Download the java file from Canvas labeled TreeDemo.java. In that file

you will find the following methods which need to be implemented :

preOrderTraversal$($Node root$)$

inOrderTraversal$($Node root$)$

$$ postOrderTraversal$($Node root$)$

@ find$($Node root, int key$)$

@ getMin$($Node root$)$

@ getMax$($Node root$)$

Create a new directory on your machine and initialize as a git repository

by using the git init command. You might want to also set a few global

defaults, refer to the slides for details. Place TreeDemo.java into that

directory and use the git add TreeDemo.java command to stage the file.

After that you can commit it by invoking the git commit $-$m "commit

message" command. You need to implement one function at a time and

make a commit to the repository. Essentially you should have at least $6$

commits to the repository, one after implementing each function.

Once you have implemented all of the functions and everything is up to

date in your working directory, you neeclass Node$\{$

int value;

Node left, right;

public Node$($int value$)\{$

this.value $=$ value;

left $=$ null;

right $=$ null;

$\}$

$\}$

class BinarySearchTree$\{$

Node root;

$/*$

recursive insert method

$*/$

$/*$

inserts a node into the tree

$*/$

public void insert$($int value$)\{$

$//$tree is empty

if$($root $==$ null$)\{$

root $=$ new Node$($value$)$;

return;

$\}$else$\{$

Node current $=$ root;

Node parent $=$ null;

while$($true$)\{$

parent $=$ current;

if$($value $$ current.value$)\{$

current $=$ current.left;

if$($current $==$ null$)\{$

parent.left $=$ new Node$($value$)$;

return;

$\}$

$\}$else$\{$

current $=$ current.right;

if$($current $==$ null$)\{$

parent.right $=$ new Node$($value$)$;

return;

$\}$

$\}$

$\}//$closing while

$\}//$closing main if$-$else

$\}$

$/*$

pre$-$order traversal

Prints the value of every node preorder

$*/$

public void preOrderTraversal$($Node root$)\{$

$//$implement in here

$\}$

$/*$

in$-$order traversal

$*/$

public void inOrderTraversal$($Node root$)\{$

$//$implement in here

$\}$

$/*$

post$-$order traversal

$*/$

public void postOrderTraversal$($Node root$)\{$

$//$implement in here

$\}$

$/*$

a method to find the node in the tree

with a specific value

$*/$

public boolean find$($Node root, int key$)\{$

$//$implement in here

$\}$

$/*$

a method to find the node in the tree

with a smallest key

$*/$

public int getMin$($Node root$)\{$

$//$implement in here

$\}$

$/*$

a method to find the node in the tree

with a largest key

$*/$

public int getMax$($Node root$)\{$

$//$implement in here

$\}$

$/*$

this method will not compile until getMax

is implemented

$*/$

public Node delete$($Node root, int key$)\{$

if$($root $==$ null$)\{$

return root;

$\}$else if$($key $$ root.value$)\{$

root.left $=$ delete$($root$.$left, key$)$;

$\}$else if$($key $>$ root.value$)\{$

root.right $=$ delete$($root$.$right, key$)$;

$\}$else$\{$

$//$node has been found

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

$//$case #$1$: leaf node

root $=$ null;

$\}$else if$($root$.$right $==$ null$)\{$

$//$case #$2$ : only left child

root $=$ root.left;

$\}$else if$($root$.$left $==$ null$)\{$

$//$case #$2$ : only right child

root $=$ root.right;

$\}$else$\{$

$//$case #$3$ : $2$ children

root.value $=$ getMax$($root$.$left$)$;

root.left $=$ delete$($root$.$left, root.value$)$;

$\}$

$\}$

return root;

$\}$

$\}$

public class TreeDemo$\{$

public static void main$($String$[]$ args$)\{$

BinarySearchTree t$1=$ new BinarySearchTree$()$;

t$1.$insert$(24)$;

t$1.$insert$(80)$;

t$1.$insert$(18)$;

t$1.$insert$(9)$;

t$1.$insert$(90)$;

t$1.$insert$(22)$;

System.out.print$("$in$-$order : $")$;

t$1.$inOrderTraversal$($t$1.$root$)$;

System.out.println$()$;

$\}$

$\}$