package BSTdemo;

/**
 * Binary Search Tree implements a BST abstract data type with the functions get and put
 * 
 * Made for UW CSE332 Sections on 2014-09-25
 * 
 * @author anied@cs.washington.edu
 * @author alonmil@cs.washington.edu
 */
public class BinarySearchTree {
	private static BinarySearchNode root;
	
	/**
	 * Tests the binary search tree by adding five nodes to it and prints them out.
	 * @param args Not used
	 */
	public static void main(String[] args) {
		// Puts in 5 entries
		put(2, "Conrad");
		put(1, "Martin");
		put(3, "Alon");
		put(5, "Matt");
		put(4, "Vivian");

		// Iterates through entries
		for(int i = 0; i < 31; i++) {
			String entry = get(i);
			if(!entry.isEmpty())
				System.out.printf("Retrieved (%02d) \"%s\"\n", i, entry);
			System.out.println();
		}
	}
	
	/**
	 * Finds a value associated with a given key
	 * @param key
	 * @return "" if the key is not found
	 */
	public static String get(int key) {
		
		BinarySearchNode node = root;
		
		while (node != null) {
			System.out.println("Looking for " + key + " at " + node.key);
			if(node.key == key)
				return node.value;
			else if(key > node.key)
				node = node.right;
			else if(key < node.key)
				node = node.left;
		}
		
		return "";
	}
	
	/**
	 * Adds a (key, value) pair to the binary search tree
	 * @param key
	 * @param value
	 */
	public static void put(int key, String value) {
		root = put(key, value, root);
	}
	
	/**
	 * Recursively explores the tree and inserts the (key, value) pair at appropriate place
	 * @param key
	 * @param value
	 * @param parent The node we are exploring
	 * @return
	 */
	private static BinarySearchNode put(int key, String value, BinarySearchNode parent) {
		if(parent == null)
			parent = new BinarySearchNode(key, value);
		else if(key > parent.key)
			parent.right = put(key, value, parent.right);
		else if(key < parent.key)
			parent.left = put(key, value, parent.left);
		
		return parent;
	}
	
	/**
	 * A class that contains a key/value pair and links to left & right children
	 */
	private static class BinarySearchNode {
		int key;
		String value;
		BinarySearchNode left;
		BinarySearchNode right;
		
		public BinarySearchNode(int key, String value) {
			this.key = key;
			this.value = value;
			
			left = null;
			right = null;
		}
	}
}