1
\$\begingroup\$

Given a Binary Tree, extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL need to be created in-place. Assume that the node structure of DLL and Binary Tree is same, only the meaning of left and right pointers are different. In DLL, left means previous pointer and right means next pointer.

The question is attributed to GeeksForGeeks. Since the code dictates not additional data structure, I am forced to extract out TreeNode class outside, rather than keeping it as an internal data structure. Looking for code-review, best practices and optimizations.

class TreesNode<T> {
    TreesNode<T> left;
    T item;
    TreesNode<T> right;

    TreesNode(T item) {
        this.item = item;
    } 
}

class BinaryTrees<T> {

    private TreesNode<T> root;

    public BinaryTrees(List<T> items) {
        create(items);
    }

    private void create (List<T> items) {        
        root = new TreesNode<T>(items.get(0));

        final Queue<TreesNode<T>> queue = new LinkedList<TreesNode<T>>();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreesNode<T> current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreesNode<T>(items.get(left));
                    queue.add(current.left);
                }
                if (right < items.size() && items.get(right) != null) {
                    current.right = new TreesNode<T>(items.get(right));
                    queue.add(current.right);
                }
            }
        }
    }


    public TreesNode<T> getRoot() {
        return root;
    }


    @Override
    public int hashCode() {
        return hashCompute(root, 0);
    }

    private int hashCompute (TreesNode<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;
        BinaryTrees<T> other = (BinaryTrees<T>) obj;
        return equal(root, other.root);
    }

    private  boolean equal(TreesNode<T> node1,  TreesNode<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);
    }

}



class DLL<T> {
    private TreesNode<T> first;
    private TreesNode<T> last;

    DLL(TreesNode<T> first) {
        this.first = first;
    }

    DLL(List<T> items) {
        for (T item : items) {
            create(item);
        }
    }

    private void create(T item) {
        TreesNode<T> node = new TreesNode<T>(item);
        if (first == null) {
            first = last = node;
        } else {
            last.right = node;
            last = node;
        }
    }

    public TreesNode<T> getFirst() {
        return first;
    }


    @Override
    public int hashCode() {
        int hashCode = 1;
        for (TreesNode<T> x = first; x != null; x = x.right)
            hashCode = 31*hashCode + x.hashCode();
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {

        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        DLL<T> other = (DLL<T>) obj;
        TreesNode<T> currentListNode = first; 
        TreesNode<T> otherListNode =  other.first;

        while (currentListNode != null && otherListNode != null) {

            if (currentListNode.item != otherListNode.item) {
                return false;
            }

            // since it is a doubly linkedlist, we check the left node too.
            if (currentListNode.left != null && currentListNode.left.item != otherListNode.left.item) {
                return false;
            }

            currentListNode = currentListNode.right;
            otherListNode = otherListNode.right;
        }


        return currentListNode == null && otherListNode == null;
    }

    public List<T> toList() {
        final List<T> list = new ArrayList<>();
        for (TreesNode<T> x = first; x != null; x = x.right) {
            list.add(x.item);
        }
        return list;
    }
}

public final class DLLConnectLeaves<T> {

    private DLLConnectLeaves() { }

    public static <T> DLL<T> dllConnectLeaves (BinaryTrees<T> btree)  {
         DLLData<T> dllData = new DLLData<>();
         recurse(btree.getRoot(), dllData);
         return new DLL<T>(dllData.first);
    }

    private static class DLLData<T> {
        private TreesNode<T> first;
        private TreesNode<T> current;
    }

    private static <T> TreesNode<T> recurse(TreesNode<T> node, DLLData<T> dll) {
        if (node == null) { return  null; }

        if (node.left == null && node.right == null) {
            if (dll.first == null) {
                dll.first = dll.current = node;
            } else {
                dll.current.right = node;
                node.left = dll.current;
                dll.current = node;
            }
            return null;
        }

        node.left = recurse (node.left, dll);
        node.right = recurse (node.right, dll);

        return node;
    }
}

public class DLLConnectLeavesTest {

    @Test
    public void test1() {
        BinaryTrees<Integer> btree1 = new BinaryTrees<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        DLL<Integer> dllActual1 =  DLLConnectLeaves.dllConnectLeaves(btree1);

        DLL<Integer> dllExpected1 = new DLL<>(Arrays.asList(4, 5, 6, 7));
        assertEquals(dllExpected1, dllActual1);

        BinaryTrees<Integer> btree1Expected = new BinaryTrees<>(Arrays.asList(1, 2, 3));
        assertEquals(btree1Expected, btree1);
    }

    @Test
    public void test2() {
        BinaryTrees<Integer> btree2 = new BinaryTrees<>(Arrays.asList(1, 2, 3, 4, null, null, 7));
        DLL<Integer> dllActual2 =  DLLConnectLeaves.dllConnectLeaves(btree2);

        DLL<Integer> dllExpected2 = new DLL<>(Arrays.asList(4, 7));
        assertEquals(dllExpected2, dllActual2);

        BinaryTrees<Integer> btree2Expected = new BinaryTrees<>(Arrays.asList(1, 2, 3));
        assertEquals(btree2Expected, btree2);
    }

    @Test
    public void test3() {
        BinaryTrees<Integer> btree3 = new BinaryTrees<>(Arrays.asList(1, 2, null, 4, null, null, null, 5));
        DLL<Integer> dllActual3 =  DLLConnectLeaves.dllConnectLeaves(btree3);

        DLL<Integer> dllExpected3 = new DLL<>(Arrays.asList(5));
        assertEquals(dllExpected3, dllActual3);

        BinaryTrees<Integer> btree3Expected = new BinaryTrees<>(Arrays.asList(1, 2, null, 4));
        assertEquals(btree3Expected, btree3);
    }

    @Test
    public void test4() {
        BinaryTrees<Integer> btree4 = new BinaryTrees<>(Arrays.asList(1, 2, 3, 4, null, null, null, 5));
        DLL<Integer> dllActual4 =  DLLConnectLeaves.dllConnectLeaves(btree4);

        DLL<Integer> dllExpected4 = new DLL<>(Arrays.asList(5, 3));
        assertEquals(dllExpected4, dllActual4);

        BinaryTrees<Integer> btree4Expected = new BinaryTrees<>(Arrays.asList(1, 2, null, 4));
        assertEquals(btree4Expected, btree4);
    }


}
\$\endgroup\$
2
\$\begingroup\$

Bug:

IndexOutOfBoundsException on empty list in BinaryTrees.create(List<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, privacy policy and cookie policy

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