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

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;
}
}

private Node<T> first;
private Node<T> last;
private int size = 0;

for (T item : items) {
}
}

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>>();

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));
}
if (right < items.size() && items.get(right) != null) {
current.right = new Node<T>(items.get(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);
}
}

/**
*
*
* 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() {
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() {
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() {
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() {
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);
}
}


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.
item = 31 * hashCompute (node.left, item) + node.hashCode();