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