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