1
\$\begingroup\$

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); 
    }
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

(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();
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.