Convert a doubly linked list into balanced binary search tree in-place

Question

Given a doubly linked list which has data members sorted in ascending order, construct a balanced binary search tree which has same data members as the given doubly linked list. The tree must be constructed in-place (no new node should be allocated for tree conversion).

This question is attributed to Geeksforgeeks. I'm looking for code review, optimizations and best practices.

class Node<T> {
 Node<T> left;
 T item;
 Node<T> right;
 Node(T item) {
 this.item = item;
 }
}
class LinkedLists<T> {
 private Node<T> first;
 private Node<T> last;
 private int size = 0;
 public LinkedLists(List<T> items) {
 for (T item : items) {
 add(item);
 }
 }
 private void add(T item) {
 Node<T> node = new Node<T>(item);
 if (first == null) {
 first = last = node;
 } else {
 last.right = node;
 node.left = last;
 last = node;
 }
 size++;
 }
 public Node<T> getFirst() {
 return first;
 }
 public int size() {
 return size;
 }
}
class BinaryTree<T> {
 private Node<T> root;
 public BinaryTree(Node<T> root) {
 this.root = root;
 }
 public BinaryTree(List<T> items) {
 create(items);
 }
 private void create (List<? extends T> items) {
 root = new Node<T>(items.get(0));
 final Queue<Node<T>> queue = new LinkedList<Node<T>>();
 queue.add(root);
 final int half = items.size() / 2;
 for (int i = 0; i < half; i++) {
 if (items.get(i) != null) {
 final Node<T> current = queue.poll(); 
 final int left = 2 * i + 1;
 final int right = 2 * i + 2;
 if (items.get(left) != null) {
 current.left = new Node<T>(items.get(left));
 queue.add(current.left);
 }
 if (right < items.size() && items.get(right) != null) {
 current.right = new Node<T>(items.get(right));
 queue.add(current.right);
 }
 }
 }
 }
 @Override
 public int hashCode() {
 return hashCompute(root, 0);
 }
 public int hashCompute (Node<T> node, int item) {
 if (node == null) return item;
 item = 31 * hashCompute (node.left, item) + node.hashCode();
 return hashCompute(node.right, item);
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj)
 return true;
 if (obj == null)
 return false;
 if (getClass() != obj.getClass())
 return false;
 BinaryTree<T> other = (BinaryTree<T>) obj;
 return equal(root, other.root);
 }
 private boolean equal(Node<T> node1, Node<T> node2) {
 if (node1 == null && node2 == null) return true;
 if (node1 == null || node2 == null) return false;
 if (node1.item != node2.item) {
 return false;
 }
 return equal(node1.left, node2.left) && equal(node1.right, node2.right);
 }
}
/**
 * 
 * http://stackoverflow.com/questions/7874517/converting-a-sorted-doubly-linked-list-to-a-bst
 * 
 * Complexity is O(n), since in each recursion, one node of DLL is taken care of.
 * 
 */
public final class DLLtoBinaryTree {
 private DLLtoBinaryTree() {}
 public static <T> Node<T> convert(LinkedLists<T> list) {
 return convert(new NodeStore<T>(list.getFirst()), list.size()); 
 }
 /**
 * Used as a mechanism to preserve the changes made in recursion tree.
 * The changes made down the tree, should be preserved when that stack frame is popped.
 */
 private static class NodeStore<T> {
 private Node<T> node = null;
 NodeStore (Node<T> newNode) {
 this.node = newNode;
 }
 }
 private static <T> Node<T> convert(NodeStore<T> ns, int n) {
 if (n <= 0) {
 return null;
 } 
 final Node<T> left = convert(ns, n/2);
 final Node<T> currNode = ns.node;
 ns.node = ns.node.right;
 currNode.left = left; 
 currNode.right = convert(ns, n - n/2 - 1);
 return currNode;
 }
}
public class DLLtoBinaryTreeTest {
 @Test
 public void test1() {
 LinkedLists<Integer> list1 = new LinkedLists<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
 Node<Integer> root1 = DLLtoBinaryTree.convert(list1); 
 BinaryTree<Integer> bstExpected1 = new BinaryTree<>(Arrays.asList(4, 2, 6, 1, 3, 5, 7));
 BinaryTree<Integer> bstActual1 = new BinaryTree<>(root1);
 assertEquals(bstExpected1, bstActual1); 
 }
 @Test
 public void test2() {
 LinkedLists<Integer> list2 = new LinkedLists<>(Arrays.asList(1, 2, 3));
 Node<Integer> root2 = DLLtoBinaryTree.convert(list2); 
 BinaryTree<Integer> bstExpected2 = new BinaryTree<>(Arrays.asList(2, 1, 3));
 BinaryTree<Integer> bstActual2 = new BinaryTree<>(root2);
 assertEquals(bstExpected2, bstActual2); 
 }
 @Test
 public void test3() {
 LinkedLists<Integer> list3 = new LinkedLists<>(Arrays.asList(1, 2, 3, 4));
 Node<Integer> root3 = DLLtoBinaryTree.convert(list3); 
 BinaryTree<Integer> bstExpected3 = new BinaryTree<>(Arrays.asList(3, 2, 4, 1));
 BinaryTree<Integer> bstActual3 = new BinaryTree<>(root3);
 assertEquals(bstExpected3, bstActual3); 
 }
 @Test
 public void test4() {
 LinkedLists<Integer> list4 = new LinkedLists<>(Arrays.asList(1, 2, 3, 4, 5, 6));
 Node<Integer> root4 = DLLtoBinaryTree.convert(list4); 
 BinaryTree<Integer> bstExpected4 = new BinaryTree<>(Arrays.asList(4, 2, 6, 1, 3, 5));
 BinaryTree<Integer> bstActual4 = new BinaryTree<>(root4);
 assertEquals(bstExpected4, bstActual4); 
 }
}

Answer 1

(Duplicated answer from here: https://codereview.stackexchange.com/a/63125/49350)

Bug:

IndexOutOfBoundsException on empty list in BinaryTree.create(List<? extends T> items). You don't have a comment stating you need to input a list containing at least something. Consider returning IllegalArgumentException and adding a comment.

---

You also have a space between a function call and its arguments here:

item = 31 * hashCompute (node.left, item) + node.hashCode();