/* 
 * SearchTree.java 
 * Implementation of binary search trees in Java.
 *
 * Author:    David Aspinall
 * Copyright: University of Edinburgh, 2001.
 *
 * SearchTree.java,v 1.3 2002/12/03 15:19:17 da Exp
 *
 */

class SearchTree implements MyCollection {
    static class Node {
	Node       left;   // left subtree
	Comparable data;   // label we can use compareTo on
	Node       right;  // right subtree
	
 	public Node(Comparable d) { // Construct a leaf
	    data = d;		    
	}
    }
    private Node root;

    // Is item in the tree?
    public boolean contains(Comparable item) {
	return contains(root, item);
    }
    private static boolean contains(Node t, Comparable item) {
	if (t == null) {
	    // Object not found in empty tree
	    return false;
	} else {
	    int cmp = t.data.compareTo(item);
	    if (cmp == 0) {
		// found the item
		return true;
	    } else if (cmp>0) {
		// data is greater than item, search left tree
		return contains(t.left, item);
	    } else {
		// data is less than item, search right tree
		return contains(t.right, item);
	    }
	}
    }
    
    // Add an item to the tree
    public void add(Comparable item) {
	root = add(root, item);
    }
    private static Node add(Node t, Comparable item) {
	if (t == null) {
	    // The (sub)tree is empty, make a new leaf node
	    return new Node(item);
	} else {
	    int cmp = t.data.compareTo(item);
	    if (cmp == 0) {
		// data is already in the tree, no change
		return t;
	    } else if (cmp>0) {
		// data is greater than item, add in left tree
		t.left = add(t.left, item);
		return t;
	    } else {
		// data is less than item, add in right tree
		t.right = add(t.right, item);
		return t;
	    }
	}
    }

    // Remove an item from the tree
    public void remove(Comparable item) {
	root = remove(root, item);
    }
    private static Node remove(Node t, Comparable item) {
 	if (t == null) {
	    // Item not found; do nothing
	    return null;
	} else {
 	    int cmp = t.data.compareTo(item);
 	    if (cmp == 0) {
		// found the item here, let's delete this node
		return deletenode(t);
	    } else if (cmp>0) {
		// data greater than item, remove from left tree
		t.left = remove(t.left, item);
		return t;
	    } else {
		// data less than item, remove from right tree
		t.right = remove(t.right, item);
		return t;
	    }
	}
    }
    
    // Delete this node from the tree.  
    // Should only be called on non-null nodes
    private static Node deletenode(Node t) {
	if (t.left == null) {
	    // Replace with right subtree
	    t = t.right;
	} else if (t.right == null) {
	    // Replace with left subtree
	    t = t.left;
	} else {
	    // Find least node in right subtree,
	    Node least = findleftmost(t.right);
	    // Copy its label here
	    t.data = least.data;
	    // Delete the least node in the right subtree.
	    t.right = deleteleftmost(t.right);
	}
	return t;
    }
    // Find leftmost node.  
    // Should only be called on non-null nodes
    private static Node findleftmost(Node t) {
	if (t.left != null) {
	    return findleftmost(t.left);
	} else {
	    return t;
	}
    }
    // Delete leftmost node.  
    // Should only be called on non-null nodes
    private static Node deleteleftmost(Node t) {
	if (t.left != null) {
	    t.left = deleteleftmost(t.left);
	    return t;
	} else {
	    // This is the leftmost node, replace it 
	    // with its right subtree.
	    return t.right;
	}
    }
    
    // String representation of tree
    public String toString() {
	return "<Binary search tree:  " + toString(root) + ">";
    }
    private static String toString(Node tree) {
	if (tree != null) {
	    return ("(" +
		    toString(tree.left) + 
		    "|" + tree.data + "|" +
		    toString(tree.right) + ")");
	} else {
	    return "";
	}
    }
}