BinaryTree

BinaryTree.java

public class BinaryTree<T extends Comparable<T>> {
    private TreeNode<T> root = null;

    public BinaryTree(TreeNode<T> r) {
	root = r;
    }

    public TreeNode<T> root() {
	return root;
    }
}

BinaryTreeBuilder.java

package Chapter4;

import java.util.HashMap;

public class BinaryTreeBuilder {
    public static <T extends Comparable<T>> BinaryTree<T> buildTree(T[] pre,
	    T[] in) {
	// initial query map
	HashMap<T, Integer> indexMap = new HashMap<>();
	for (int i = 0; i < pre.length; i++)
	    indexMap.put(in[i], i);

	return new BinaryTree<T>(buildTree(indexMap, pre, in, 0, 0, in.length));
    }

    public static <T extends Comparable<T>> TreeNode<T> buildTree(
	    HashMap<T, Integer> indexMap, T[] pre, T[] in, int preLo, int inLo, int size) {
	// base case
	if (size <= 0)
	    return null;

	TreeNode<T> rootNode = new TreeNode<T>(pre[preLo]);
	int inOrderIndex = indexMap.get(rootNode.key);
	int leftSubTreeSize = inOrderIndex - inLo;
	int rightSubTreeSize = size - leftSubTreeSize - 1;
	rootNode.left = buildTree(indexMap, pre, in, preLo + 1, inLo,
		leftSubTreeSize);
	rootNode.right = buildTree(indexMap, pre, in, preLo + leftSubTreeSize
		+ 1, inOrderIndex + 1, rightSubTreeSize);
	if(rootNode.left != null)
	    rootNode.left.parent =  rootNode;
	if(rootNode.right != null)
	    rootNode.right.parent =  rootNode;
	return rootNode;
    }

}

BST.java

package Chapter4;

public class BST<T extends Comparable<T>> {
    private TreeNode<T> root = null;

    public BST(TreeNode<T> r) {
	root = r;
    }

    public TreeNode<T> root() {
	return root;
    }
    
    public void insert(T key) {
	if(root == null) root = new TreeNode<T>(key, null, null);
	TreeNode<T> cur = root;
	TreeNode<T> prev = null;
	while(cur != null) {
	    prev = cur;
	    if(key.compareTo(cur.key) <= 0)
		cur = cur.left;
	    else
		cur = cur.right;
	}
	
	if(key.compareTo(prev.key) <= 0)
	    prev.left = new TreeNode<T>(key, null, null);
	else
	    prev.right = new TreeNode<T>(key, null, null);
    }
}

TreeNode.java

package Chapter4;

public class TreeNode<T extends Comparable<T>> {
    public TreeNode<T> left;
    public TreeNode<T> right;
    public TreeNode<T> parent;
    public T key;
    
    public TreeNode(T k){
	key = k;
    }
    
    public TreeNode(T k, TreeNode<T> l, TreeNode<T> r){
	key = k;
	left = l;
	right= r;
    }
    
    public TreeNode(T k, TreeNode<T> l, TreeNode<T> r, TreeNode<T> p){
	key = k;
	left = l;
	right= r;
	parent = p;
    }
}