BST Reconstruct

reconstruct

/**
 * First clears this BST, then reconstructs the BST that is
 * uniquely defined by the given preorder and inorder traversals
 * 
 * (When you finish, this BST should produce the same preorder and
 * inorder traversals as those given)
 * 
 * @param preorder a preorder traversal of the BST to reconstruct
 * @param inorder an inorder traversal of the BST to reconstruct
 */

public void reconstruct(List<? extends T> preorder, List<? extends T> inorder) {
	if(preorder == null){
		throw new NullPointerException("Cannot build a tree if preorder is null");
	}
	clear();
	root = reconstruct(preorder, inorder, 0, 0, preorder.size());
}
private Node<T> reconstruct(List<? extends T> preorder, List<? extends T> inorder, int p, int q, int length){
	if(preorder == null || length ==0){
		return null;
	}
	Node<T> node = new Node<T>(preorder.get(p));
	int offset = searchInInorder(inorder, 	preorder.get(p), q);
	node.left = reconstruct(preorder, inorder, p + 1, q, offset);
	node.right = reconstruct(preorder, inorder, p + offset + 1, q + offset + 1,length - (offset + 1));	
	return node;			
}
private  int searchInInorder(List<? extends T> inorder, T key, int index) {
	int offset = 0;
	for (int i = index; i < inorder.size(); i++) {
		if(inorder.get(i) == null && key == null){
			return offset;
		}
		if (inorder.get(i).compareTo(key) == 0 ) {
			return offset;
		}	
		offset++;
	}
	return -1;
}