Extract Leaves of a Binary Tree in a Doubly Linked List

Question

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

• Ivan Ivanov: Is recursion allowed?
• rolfl: This, and other posts, are being discussed on meta

Answer 1

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