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);     }}
Convert a doubly linked list into balanced binary search tree in-place
java;algorithm;linked list;tree