# Binary Search Tree

Page 1 of 1

## 2 Replies - 2677 Views - Last Post: 01 November 2011 - 04:22 PM

### #1 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

# Binary Search Tree

Posted 10 August 2011 - 04:14 PM

Description: To run, change into the directory where BST.java is located and type:

javac BST.java
java BSTAn unbalanced node-based binary search tree.
```/**
* BST.java
*
* An unbalanced node-based binary search tree. On average, operations are O(log(n)).
* Removing nodes can quickly linearize the tree so that some operations become O(n).
* For O(log(n)) operations in the worst case, use AVL or Red-Black Trees: {@link http://en.wikipedia.org/wiki/AVL%20tree}.
* Inserting, removing, and searching rely on Comparable.CompareTo.
*
* @author Ryan Beckett
* @version 1.0
* JDK 1.7
* 10/16/2011
*
*/
public class BST<T extends Comparable<? super T>> {

private Node<T>	treeRoot;

/**
* Insert a value into the tree.
*/
public void insert(T val) {
if(treeRoot == null) {
treeRoot = new Node<T>(val);
}else {
insert(treeRoot, val);
}
}

private void insert(Node<T> root, T val) {
if(val.compareTo(root.val) <= 0) {
if(root.left == null) { //insert as left child
root.left = new Node<T>(val);
}else { //traverse left subtree
insert(root.left, val);
}
}else if(val.compareTo(root.val) > 0) {
if(root.right == null) { //insert as right child
root.right = new Node<T>(val);
}else { //traverse right subtree
insert(root.right, val);
}
}
}

private void insert(Node<T> nd) {
if(nd == null)return;
if(treeRoot == null) { //create tree root
treeRoot = nd;
}else { //insert into tree
insert(treeRoot, nd);
}
}

private void insert(Node<T> root, Node<T> nd) {
if(nd.val.compareTo(root.val) <= 0) {
if(root.left == null) { //insert as left child
root.left = nd;
}else { //traverse left subtree
insert(root.left, nd);
}
}else if(nd.val.compareTo(root.val) > 0) {
if(root.right == null) { //insert as right child
root.right = nd;
}else { //traverse right subtree
insert(root.right, nd);
}
}
}

/**
* Search for a value in the tree.
*/
public Node<T> search(T val) {
return search(treeRoot, val);
}

private Node<T> search( Node<T> root, T val ) {
if(root == null)return null;
if(val.compareTo(root.val) < 0) //traverse left subtree
return search(root.left, val);
else if(val.compareTo(root.val) > 0)//traverse right subtree
return search(root.right, val);
else //found target
return root;
}

/**
* Perform an in-order tree traversal. Display the tree elements in ascending order.
*/
public void print() {
System.out.print("Tree: ");
if(treeRoot == null) {
System.out.println();
return;
}
print(treeRoot);
System.out.println();
}

private void print( Node<T> root ) {
if(root.left != null) //traverse left subtree first
print( root.left );
System.out.print( root + ", " ); //now visit the node
if(root.right != null)
print( root.right ); //traverse right subtree after
}

/**
* Remove a value from the tree and return its node.
*/
public Node<T> remove(T val) {
return remove(treeRoot, treeRoot, val);
}

private Node<T> remove(Node<T> root, Node<T> parent, T val) {
if(val.compareTo(root.val) < 0) { //traverse left subtree
return remove(root.left, root, val);
}else if(val.compareTo(root.val) > 0) { //traverse right subtree
return remove(root.right, root, val);
}else {//found node; link root's parent to one of root's children
return root;
}
}

/**
* Remove node by letting one of its children take its place.
*/
private void adjust(Node<T> root, Node<T> parent) {
//We're removing a leaf
if(root.left == null && root.right == null) {
if(root == treeRoot) {//We're removing the root of tree, just clear the tree.
treeRoot = null;
}else if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = null;
}else { //it's its parent's right child
parent.right = null;
}
}
//We're removing an interior node with two children
else if(root.right != null && root.left !=  null) {
Node<T> removable = root.right.left; //temporarily hold the node's right child's left subtree
root.right.left = root.left; //make the node's left subtree the node's right child's left subtree
if(root == treeRoot) { //We're removing the root of the tree
treeRoot = root.right; //the node's right child becomes the tree root
}else {
parent.right = root.right; //replace node with its right child
}
insert(removable); //add the node's right child's left subtree back into the tree;
}
//We're removing an interior node with one child
else {
if(root.left != null) { //node has left child only
if(root == treeRoot) { //left child becomes tree root
treeRoot = root.left;
}else {
if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = root.left;
}else {//it is its parent's right child
parent.right = root.left;
}
}
}else { //node has right child only
if(root == treeRoot) { //right child becomes tree root
treeRoot = root.right;
}else {
if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = root.right;
}else {//it is its parent's right child
parent.right = root.right;
}
}
}
}
}

/**
* Clear the tree.
*/
public void clear() {
treeRoot = null;
}

/* Test Driver */
public static void main( String args[] ) {

///////////////////
//Integer example
///////////////////
System.out.println("---------------------nInteger list examplen---------------------");
BST<Integer> t = new BST<Integer>();

///////////////////
//Inserting
///////////////////
t.insert( 5 );
t.insert( 2 );
t.insert( 7 );
t.insert( 1 );
t.insert( 5 );
t.insert( 3 );
t.insert( 6 );
t.insert( 10 );
t.insert( 3 );
t.print();

///////////////////
//Searching
///////////////////
int target = 10;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}
target = 0;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}
target = 2;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}

///////////////////
//Removing
///////////////////
System.out.println("Removing 11");
t.remove(11);
t.print();
System.out.println("Removing 5");
t.remove(5);
t.print();
System.out.println("Removing 1");
t.remove(1);
t.print();
System.out.println("Removing 6");
t.remove(6);
t.print();
System.out.println("Removing 10");
t.remove(10);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();

///////////////////
//String example
///////////////////
System.out.println("n---------------------nString list examplen---------------------");
BST<String> s = new BST<String>();

///////////////////
//Inserting
///////////////////
s.insert( "foo" );
s.insert( "?>}|");
s.insert( "bar" );
s.insert( "qux" );
s.insert( "baz" );
s.insert( "?>");
s.insert( "qux" );
s.print();

///////////////////
//Searching
///////////////////
String strTarget = "?>}";
if(s.search(strTarget) != null)
{
System.out.println(strTarget+" was found");
}else {
}
strTarget = "bar";
if(s.search(strTarget) != null)
{
System.out.println(strTarget+" was found");
}else {
}

///////////////////
//Removing
///////////////////
System.out.println("Removing bar");
s.remove( "bar" );
s.print();
System.out.println("Removing baz");
s.remove( "baz" );
s.print();
System.out.println("Removing qux");
s.remove( "qux" );
s.print();
System.out.println("Removing ?>}|");
s.remove( "?>}|" );
s.print();
System.out.println("Removing ?>}|");
s.remove( "?>}|" );
s.print();
}
}

class Node<T extends Comparable<? super T>> {

T	val;
Node<T>	left, right;

Node( T val ) {
this.val = val;
}

public String toString() {
return val.toString();
}
}

```

Is This A Good Question/Topic? 0

## Replies To: Binary Search Tree

### #2 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Binary Search Tree

Posted 10 August 2011 - 04:14 PM

Description: To run, change into the directory where BST.java is located and type:

javac BST.java
java BSTAn unbalanced node-based binary search tree.
```/**
* BST.java
*
* An unbalanced node-based binary search tree. On average, operations are O(log(n)).
* Removing nodes can quickly linearize the tree so that some operations become O(n).
* For O(log(n)) operations in the worst case, use AVL or Red-Black Trees: {@link http://en.wikipedia.org/wiki/AVL%20tree}.
* Inserting, removing, and searching rely on Comparable.CompareTo.
*
* @author Ryan Beckett
* @version 1.0
* JDK 1.7
* 10/16/2011
*
*/
public class BST<T extends Comparable<? super T>> {

private Node<T>	treeRoot;

/**
* Insert a value into the tree.
*/
public void insert(T val) {
if(treeRoot == null) {
treeRoot = new Node<T>(val);
}else {
insert(treeRoot, val);
}
}

private void insert(Node<T> root, T val) {
if(val.compareTo(root.val) <= 0) {
if(root.left == null) { //insert as left child
root.left = new Node<T>(val);
}else { //traverse left subtree
insert(root.left, val);
}
}else if(val.compareTo(root.val) > 0) {
if(root.right == null) { //insert as right child
root.right = new Node<T>(val);
}else { //traverse right subtree
insert(root.right, val);
}
}
}

private void insert(Node<T> nd) {
if(nd == null)return;
if(treeRoot == null) { //create tree root
treeRoot = nd;
}else { //insert into tree
insert(treeRoot, nd);
}
}

private void insert(Node<T> root, Node<T> nd) {
if(nd.val.compareTo(root.val) <= 0) {
if(root.left == null) { //insert as left child
root.left = nd;
}else { //traverse left subtree
insert(root.left, nd);
}
}else if(nd.val.compareTo(root.val) > 0) {
if(root.right == null) { //insert as right child
root.right = nd;
}else { //traverse right subtree
insert(root.right, nd);
}
}
}

/**
* Search for a value in the tree.
*/
public Node<T> search(T val) {
return search(treeRoot, val);
}

private Node<T> search( Node<T> root, T val ) {
if(root == null)return null;
if(val.compareTo(root.val) < 0) //traverse left subtree
return search(root.left, val);
else if(val.compareTo(root.val) > 0)//traverse right subtree
return search(root.right, val);
else //found target
return root;
}

/**
* Perform an in-order tree traversal. Display the tree elements in ascending order.
*/
public void print() {
System.out.print("Tree: ");
if(treeRoot == null) {
System.out.println();
return;
}
print(treeRoot);
System.out.println();
}

private void print( Node<T> root ) {
if(root.left != null) //traverse left subtree first
print( root.left );
System.out.print( root + ", " ); //now visit the node
if(root.right != null)
print( root.right ); //traverse right subtree after
}

/**
* Remove a value from the tree and return its node.
*/
public Node<T> remove(T val) {
return remove(treeRoot, treeRoot, val);
}

private Node<T> remove(Node<T> root, Node<T> parent, T val) {
if(val.compareTo(root.val) < 0) { //traverse left subtree
return remove(root.left, root, val);
}else if(val.compareTo(root.val) > 0) { //traverse right subtree
return remove(root.right, root, val);
}else {//found node; link root's parent to one of root's children
return root;
}
}

/**
* Remove node by letting one of its children take its place.
*/
private void adjust(Node<T> root, Node<T> parent) {
//We're removing a leaf
if(root.left == null && root.right == null) {
if(root == treeRoot) {//We're removing the root of tree, just clear the tree.
treeRoot = null;
}else if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = null;
}else { //it's its parent's right child
parent.right = null;
}
}
//We're removing an interior node with two children
else if(root.right != null && root.left !=  null) {
Node<T> removable = root.right.left; //temporarily hold the node's right child's left subtree
root.right.left = root.left; //make the node's left subtree the node's right child's left subtree
if(root == treeRoot) { //We're removing the root of the tree
treeRoot = root.right; //the node's right child becomes the tree root
}else {
parent.right = root.right; //replace node with its right child
}
insert(removable); //add the node's right child's left subtree back into the tree;
}
//We're removing an interior node with one child
else {
if(root.left != null) { //node has left child only
if(root == treeRoot) { //left child becomes tree root
treeRoot = root.left;
}else {
if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = root.left;
}else {//it is its parent's right child
parent.right = root.left;
}
}
}else { //node has right child only
if(root == treeRoot) { //right child becomes tree root
treeRoot = root.right;
}else {
if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = root.right;
}else {//it is its parent's right child
parent.right = root.right;
}
}
}
}
}

/**
* Clear the tree.
*/
public void clear() {
treeRoot = null;
}

private class Node<T extends Comparable<? super T>> {

T	val;
Node<T>	left, right;

Node( T val ) {
this.val = val;
}

public String toString() {
return val.toString();
}
}

/* Test Driver */
public static void main( String args[] ) {

///////////////////
//Integer example
///////////////////
System.out.println("---------------------nInteger list examplen---------------------");
BST<Integer> t = new BST<Integer>();

///////////////////
//Inserting
///////////////////
t.insert( 5 );
t.insert( 2 );
t.insert( 7 );
t.insert( 1 );
t.insert( 5 );
t.insert( 3 );
t.insert( 6 );
t.insert( 10 );
t.insert( 3 );
t.print();

///////////////////
//Searching
///////////////////
int target = 10;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}
target = 0;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}
target = 2;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}

///////////////////
//Removing
///////////////////
System.out.println("Removing 11");
t.remove(11);
t.print();
System.out.println("Removing 5");
t.remove(5);
t.print();
System.out.println("Removing 1");
t.remove(1);
t.print();
System.out.println("Removing 6");
t.remove(6);
t.print();
System.out.println("Removing 10");
t.remove(10);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();

///////////////////
//String example
///////////////////
System.out.println("n---------------------nString list examplen---------------------");
BST<String> s = new BST<String>();

///////////////////
//Inserting
///////////////////
s.insert( "foo" );
s.insert( "?>}|");
s.insert( "bar" );
s.insert( "qux" );
s.insert( "baz" );
s.insert( "?>");
s.insert( "qux" );
s.print();

///////////////////
//Searching
///////////////////
String strTarget = "?>}";
if(s.search(strTarget) != null)
{
System.out.println(strTarget+" was found");
}else {
}
strTarget = "bar";
if(s.search(strTarget) != null)
{
System.out.println(strTarget+" was found");
}else {
}

///////////////////
//Removing
///////////////////
System.out.println("Removing bar");
s.remove( "bar" );
s.print();
System.out.println("Removing baz");
s.remove( "baz" );
s.print();
System.out.println("Removing qux");
s.remove( "qux" );
s.print();
System.out.println("Removing ?>}|");
s.remove( "?>}|" );
s.print();
System.out.println("Removing ?>}|");
s.remove( "?>}|" );
s.print();
}
}

```

### #3 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Binary Search Tree

Posted 10 August 2011 - 04:14 PM

Description: To run, change into the directory where BST.java is located and type:

javac BST.java
java BSTAn unbalanced node-based binary search tree.
```/**
* BST.java
*
* An unbalanced node-based binary search tree. On average, operations are O(log(n)).
* Removing nodes can quickly linearize the tree so that some operations become O(n).
* For O(log(n)) operations in the worst case, use AVL or Red-Black Trees: {@link http://en.wikipedia.org/wiki/AVL%20tree}.
* Inserting, removing, and searching rely on Comparable.CompareTo.
*
* @author Ryan Beckett
* @version 1.0
* JDK 1.7
* 10/16/2011
*
*/
public class BST<T extends Comparable<? super T>> {

private Node<T>	treeRoot;

/**
* Insert a value into the tree.
*/
public void insert(T val) {
if(treeRoot == null) {
treeRoot = new Node<T>(val);
}else {
insert(treeRoot, val);
}
}

private void insert(Node<T> root, T val) {
if(val.compareTo(root.val) <= 0) {
if(root.left == null) { //insert as left child
root.left = new Node<T>(val);
}else { //traverse left subtree
insert(root.left, val);
}
}else if(val.compareTo(root.val) > 0) {
if(root.right == null) { //insert as right child
root.right = new Node<T>(val);
}else { //traverse right subtree
insert(root.right, val);
}
}
}

private void insert(Node<T> nd) {
if(nd == null)return;
if(treeRoot == null) { //create tree root
treeRoot = nd;
}else { //insert into tree
insert(treeRoot, nd);
}
}

private void insert(Node<T> root, Node<T> nd) {
if(nd.val.compareTo(root.val) <= 0) {
if(root.left == null) { //insert as left child
root.left = nd;
}else { //traverse left subtree
insert(root.left, nd);
}
}else if(nd.val.compareTo(root.val) > 0) {
if(root.right == null) { //insert as right child
root.right = nd;
}else { //traverse right subtree
insert(root.right, nd);
}
}
}

/**
* Search for a value in the tree.
*/
public T search(T val) {
Node<T> res = search(treeRoot, val);
if(res == null)return null;
else return res.val;
}

private Node<T> search( Node<T> root, T val ) {
if(root == null)return null;
if(val.compareTo(root.val) < 0) //traverse left subtree
return search(root.left, val);
else if(val.compareTo(root.val) > 0)//traverse right subtree
return search(root.right, val);
else //found target
return root;
}

/**
* Perform an in-order tree traversal. Display the tree elements in ascending order.
*/
public void print() {
System.out.print("Tree: ");
if(treeRoot == null) {
System.out.println();
return;
}
print(treeRoot);
System.out.println();
}

private void print( Node<T> root ) {
if(root.left != null) //traverse left subtree first
print( root.left );
System.out.print( root + ", " ); //now visit the node
if(root.right != null)
print( root.right ); //traverse right subtree after
}

/**
* Remove a value from the tree and return its node.
*/
public T remove(T val) {
Node<T> res = remove(treeRoot, treeRoot, val);
if(res == null)return null;
else return res.val;
}

private Node<T> remove(Node<T> root, Node<T> parent, T val) {
if(val.compareTo(root.val) < 0) { //traverse left subtree
return remove(root.left, root, val);
}else if(val.compareTo(root.val) > 0) { //traverse right subtree
return remove(root.right, root, val);
}else {//found node; link root's parent to one of root's children
return root;
}
}

/**
* Remove node by letting one of its children take its place.
*/
private void adjust(Node<T> root, Node<T> parent) {
//We're removing a leaf
if(root.left == null && root.right == null) {
if(root == treeRoot) {//We're removing the root of tree, just clear the tree.
treeRoot = null;
}else if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = null;
}else { //it's its parent's right child
parent.right = null;
}
}
//We're removing an interior node with two children
else if(root.right != null && root.left !=  null) {
Node<T> removable = root.right.left; //temporarily hold the node's right child's left subtree
root.right.left = root.left; //make the node's left subtree the node's right child's left subtree
if(root == treeRoot) { //We're removing the root of the tree
treeRoot = root.right; //the node's right child becomes the tree root
}else {
parent.right = root.right; //replace node with its right child
}
insert(removable); //add the node's right child's left subtree back into the tree;
}
//We're removing an interior node with one child
else {
if(root.left != null) { //node has left child only
if(root == treeRoot) { //left child becomes tree root
treeRoot = root.left;
}else {
if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = root.left;
}else {//it is its parent's right child
parent.right = root.left;
}
}
}else { //node has right child only
if(root == treeRoot) { //right child becomes tree root
treeRoot = root.right;
}else {
if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
parent.left = root.right;
}else {//it is its parent's right child
parent.right = root.right;
}
}
}
}
}

/**
* Clear the tree.
*/
public void clear() {
treeRoot = null;
}

private class Node<T extends Comparable<? super T>> {

T	val;
Node<T>	left, right;

Node( T val ) {
this.val = val;
}

public String toString() {
return val.toString();
}
}

/* Test Driver */
public static void main( String args[] ) {

///////////////////
//Integer example
///////////////////
System.out.println("---------------------nInteger list examplen---------------------");
BST<Integer> t = new BST<Integer>();

///////////////////
//Inserting
///////////////////
t.insert( 5 );
t.insert( 2 );
t.insert( 7 );
t.insert( 1 );
t.insert( 5 );
t.insert( 3 );
t.insert( 6 );
t.insert( 10 );
t.insert( 3 );
t.print();

///////////////////
//Searching
///////////////////
int target = 10;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}
target = 0;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}
target = 2;
if(t.search(target) != null)
{
System.out.println(target+" was found");
}else {
}

///////////////////
//Removing
///////////////////
System.out.println("Removing 11");
t.remove(11);
t.print();
System.out.println("Removing 5");
t.remove(5);
t.print();
System.out.println("Removing 1");
t.remove(1);
t.print();
System.out.println("Removing 6");
t.remove(6);
t.print();
System.out.println("Removing 10");
t.remove(10);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();

///////////////////
//String example
///////////////////
System.out.println("n---------------------nString list examplen---------------------");
BST<String> s = new BST<String>();

///////////////////
//Inserting
///////////////////
s.insert( "foo" );
s.insert( "?>}|");
s.insert( "bar" );
s.insert( "qux" );
s.insert( "baz" );
s.insert( "?>");
s.insert( "qux" );
s.print();

///////////////////
//Searching
///////////////////
String strTarget = "?>}";
if(s.search(strTarget) != null)
{
System.out.println(strTarget+" was found");
}else {
}
strTarget = "bar";
if(s.search(strTarget) != null)
{
System.out.println(strTarget+" was found");
}else {
}

///////////////////
//Removing
///////////////////
System.out.println("Removing bar");
s.remove( "bar" );
s.print();
System.out.println("Removing baz");
s.remove( "baz" );
s.print();
System.out.println("Removing qux");
s.remove( "qux" );
s.print();
System.out.println("Removing ?>}|");
s.remove( "?>}|" );
s.print();
System.out.println("Removing ?>}|");
s.remove( "?>}|" );
s.print();
}
}

```

### #4 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Binary Search Tree

Posted 10 August 2011 - 04:14 PM

Description: To run, change into the directory where BST.java is located and type:

javac BST.java
java BSTAn unbalanced node-based binary search tree.
```/**
* <p>
* An unbalanced node-based binary search tree. On average, operations are done
* in logarithmic time. Removing nodes can quickly linearize the tree so that
* some operations are done in linear time. For logarithmic runtime across all
* operations in the worst case, use AVL or Red-Black Trees. Inserting,
* removing, and searching rely on {@link Comparable#compareTo(Object) Comparable.compareTo}. The tree
* </p>
*
* @author Ryan Beckett
* @version 1.0
*
*/
public class BST<T extends Comparable<? super T>> {

private Node<T> treeRoot;

/**
* Insert a value into the tree.
*
* @param val
*            The value to be inserted in the tree.
*/
public void insert(T val) {
if (val == null)
return;
else if (treeRoot == null) // create tree root
treeRoot = new Node<T>(val);
else
// insert into the tree
insert(treeRoot, val);
}

private void insert(Node<T> root, T val) {
if (val.compareTo(root.val) <= 0) {
if (root.left == null) { // insert as left child
root.left = new Node<T>(val);
} else { // traverse left subtree
insert(root.left, val);
}
} else if (val.compareTo(root.val) > 0) {
if (root.right == null) { // insert as right child
root.right = new Node<T>(val);
} else { // traverse right subtree
insert(root.right, val);
}
}
}

private void insert(Node<T> nd) {
if (nd == null)
return;
if (treeRoot == null) // create tree root
treeRoot = nd;
else
// insert into the tree
insert(treeRoot, nd);
}

private void insert(Node<T> root, Node<T> nd) {
if (nd.val.compareTo(root.val) <= 0) {
if (root.left == null) { // insert as left child
root.left = nd;
} else { // traverse left subtree
insert(root.left, nd);
}
} else if (nd.val.compareTo(root.val) > 0) {
if (root.right == null) { // insert as right child
root.right = nd;
} else { // traverse right subtree
insert(root.right, nd);
}
}
}

/**
* Search for a value in the tree.
*
* @param val
*            The value to be searched for in the tree.
*/
public T search(T val) {
if (val == null)
return null;
Node<T> res = search(treeRoot, val);
if (res == null)
return null;
else
return res.val;
}

private Node<T> search(Node<T> root, T val) {
if (root == null)
return null;
if (val.compareTo(root.val) < 0) // traverse left subtree
return search(root.left, val);
else if (val.compareTo(root.val) > 0)// traverse right subtree
return search(root.right, val);
else
// found target
return root;
}

/**
* Perform an in-order tree traversal. Display the tree elements in
* ascending order.
*/
public void print() {
System.out.print("Tree: ");
if (treeRoot == null) {
System.out.println();
return;
}
print(treeRoot);
System.out.println();
}

private void print(Node<T> root) {
if (root.left != null) // traverse left subtree first
print(root.left);
System.out.print(root + ", "); // now visit the node
if (root.right != null)
print(root.right); // traverse right subtree after
}

/**
* Remove a value from the tree and return it.
*
* @param val
*            The value to be removed from the tree.
*/
public T remove(T val) {
if (val == null)
return null;
Node<T> res = remove(treeRoot, treeRoot, val);
if (res == null)
return null;
else
return res.val;
}

private Node<T> remove(Node<T> root, Node<T> parent, T val) {
if (root == null)
if (val.compareTo(root.val) < 0) { // traverse left subtree
return remove(root.left, root, val);
} else if (val.compareTo(root.val) > 0) { // traverse right subtree
return remove(root.right, root, val);
} else {// found node; link root's parent to one of root's children
return root;
}
}

/**
* Remove node by letting one of its children take its place.
*/
private void adjust(Node<T> root, Node<T> parent) {
// We're removing a leaf
if (root.left == null && root.right == null) {
if (root == treeRoot) {// We're removing the root of tree, just
// clear the tree.
treeRoot = null;
} else if (root.val.compareTo(parent.val) <= 0) { // it is its
// parent's left
// child
parent.left = null;
} else { // it's its parent's right child
parent.right = null;
}
}
// We're removing an interior node with two children
else if (root.right != null && root.left != null) {
Node<T> removable = root.right.left; // temporarily hold the node's
// right child's left subtree
root.right.left = root.left; // make the node's left subtree the
// node's right child's left subtree
if (root == treeRoot) { // We're removing the root of the tree
treeRoot = root.right; // the node's right child becomes the
// tree root
} else {
parent.right = root.right; // replace node with its right child
}
insert(removable); // add the node's right child's left subtree back
// into the tree;
}
// We're removing an interior node with one child
else {
if (root.left != null) { // node has left child only
if (root == treeRoot) { // left child becomes tree root
treeRoot = root.left;
} else {
if (root.val.compareTo(parent.val) <= 0) { // it is its
// parent's left
// child
parent.left = root.left;
} else {// it is its parent's right child
parent.right = root.left;
}
}
} else { // node has right child only
if (root == treeRoot) { // right child becomes tree root
treeRoot = root.right;
} else {
if (root.val.compareTo(parent.val) <= 0) { // it is its
// parent's left
// child
parent.left = root.right;
} else {// it is its parent's right child
parent.right = root.right;
}
}
}
}
}

/**
* Clear the tree.
*/
public void clear() {
treeRoot = null;
}

private class Node<T extends Comparable<? super T>> {

T val;
Node<T> left, right;

Node(T val) {
this.val = val;
}

public String toString() {
return val.toString();
}
}
}

class BSTTest {

/* Test Driver */
public static void main(String args[]) {

// /////////////////
// Integer example
// /////////////////
System.out
.println("---------------------nInteger list examplen---------------------");
BST<Integer> t = new BST<Integer>();

// /////////////////
// Inserting
// /////////////////
t.insert(5);
t.insert(2);
t.insert(7);
t.insert(1);
t.insert(5);
t.insert(3);
t.insert(6);
t.insert(10);
t.insert(3);
t.print();

// /////////////////
// Searching
// /////////////////
int target = 10;
if (t.search(target) != null) {
System.out.println(target + " was found");
} else {
}
target = 0;
if (t.search(target) != null) {
System.out.println(target + " was found");
} else {
}
target = 2;
if (t.search(target) != null) {
System.out.println(target + " was found");
} else {
}

// /////////////////
// Removing
// /////////////////
System.out.println("Removing 11");
t.remove(11);
t.print();
System.out.println("Removing 5");
t.remove(5);
t.print();
System.out.println("Removing 1");
t.remove(1);
t.print();
System.out.println("Removing 6");
t.remove(6);
t.print();
System.out.println("Removing 10");
t.remove(10);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();
System.out.println("Removing 3");
t.remove(3);
t.print();

// /////////////////
// String example
// /////////////////
System.out
.println("n---------------------nString list examplen---------------------");
BST<String> s = new BST<String>();

// /////////////////
// Inserting
// /////////////////
s.insert("foo");
s.insert("?>}|");
s.insert("bar");
s.insert("qux");
s.insert("baz");
s.insert("?>");
s.insert("qux");
s.print();

// /////////////////
// Searching
// /////////////////
String strTarget = "?>}";
if (s.search(strTarget) != null) {
System.out.println(strTarget + " was found");
} else {
}
strTarget = "bar";
if (s.search(strTarget) != null) {
System.out.println(strTarget + " was found");
} else {
}

// /////////////////
// Removing
// /////////////////
System.out.println("Removing bar");
s.remove("bar");
s.print();
System.out.println("Removing baz");
s.remove("baz");
s.print();
System.out.println("Removing qux");
s.remove("qux");
s.print();
System.out.println("Removing ?>}|");
s.remove("?>}|");
s.print();
System.out.println("Removing ?>}|");
s.remove("?>}|");
s.print();
}
}

```

### #5 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Binary Search Tree

Posted 16 October 2011 - 03:03 AM

Changes on 10/16/2011: Fixed a bug in BST.adjust(). Allows duplicate data.

### #6 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Binary Search Tree

Posted 01 November 2011 - 04:22 PM

Changes on 11/1/2011: BST.search(T val) and BST.remove(T val) return an instance of T instead of Node, which is private to BST.