Problem
I’m looking for corrections, optimizations, general code review, etc.
final class TreeData<T> {
private T item;
private boolean left;
private boolean right;
public TreeData(T item) {
this.item = item;
}
public T getData () {
return item;
}
public boolean getLeft() {
return left;
}
public void setLeft(boolean left) {
this.left = left;
}
public boolean getRight() {
return right;
}
public void setRight(boolean right) {
this.right = right;
}
public boolean isLeaf () {
return !left && !right;
}
}
/**
* There are 2 common approaches over the internet:
*
* 1. Preorder deserialization.
* Cost: (2 * nodeSize * (n + 1))
*
* 2. PreOrder and Inorder deserialization
* Cost: (2 * nodeSize * (n))
*
* 3. Object based (wrap node inside an object, with a boolean
* Cost: (1 * (nodeSize + boolean + 8(object overhead)) * n )
*
* The third option triumphs iff:
* (nodeSize + boolean + 8) < (2 * nodeSize)
* boolean + 8 < nodeSize
* 1 + 8 < nodeSize
*
* When a node is saves as an Integer, then the nodeSize is (4 + 8 => 12)
* So
* 9 < 12.
* Thus works :)
*
* OR:
*
* Simply consider a single tree with 1 node, of type Int.
* Pre + Inorder is = 2 * (8(int object) + 4(actual value)) * 1 => 24
* Object with boolean = 1 * (8(wrapper object) + 12(int object) + 2) * 1 => 22.
*
*
* Complexity: O(n)
*
*/
public final class SerializeDeserializeBinarytree<T> {
TreeNode<T> root;
public SerializeDeserializeBinarytree(List<T> items) {
if (items == null) throw new NullPointerException("the items cannot be null");
create(items);
}
/** construction using parent child relation that left child is 2i + 1 and right is 2i + 2 */
@SuppressWarnings("unchecked")
private void create (List<T> items) {
assert items != null;
root = new TreeNode<T>(null, items.get(0), null);
final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode<T> current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode<T>(null, items.get(left), null);
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<T>(null, items.get(right), null);
queue.add(current.right);
}
}
}
}
private static class TreeNode<T> {
TreeNode<T> left;
T item;
TreeNode<T> right;
TreeNode (TreeNode<T> left, T item, TreeNode<T> right) {
this.left = left;
this.item = item;
this.right = right;
}
}
public List<TreeData<T>> serialize () {
if (root == null) {
throw new NoSuchElementException("The root should be non-null");
}
List<TreeData<T>> objectList = new ArrayList<TreeData<T>>(countNodes(root));
preorderSerialize(root, objectList);
return Collections.unmodifiableList(objectList);
}
private int countNodes(TreeNode<T> root) {
assert root != null;
if (root != null) {
return countNodes(root.left) + countNodes(root.right) + 1;
}
return 0;
}
private boolean preorderSerialize(TreeNode<T> node, List<TreeData<T>> objectList ) {
assert root != null;
assert objectList != null;
if (node != null) {
TreeData<T> treeData = new TreeData<T>(node.item);
objectList.add(treeData);
treeData.setLeft(preorderSerialize (node.left, objectList));
treeData.setRight(preorderSerialize (node.right, objectList));
return true;
}
return false;
}
private class CounterContainer {
private int counterContainer;
public CounterContainer(int counterContainer) {
this.counterContainer = counterContainer;
}
public void increment() {
counterContainer++;
}
public int getCounter () {
return counterContainer;
}
}
public void deserialize (List<TreeData<T>> treeDatas) {
if (treeDatas == null) throw new NullPointerException("The treeData should not be null");
root = preOrderDeserialize (treeDatas, new CounterContainer(0));
}
private TreeNode<T> preOrderDeserialize (List<TreeData<T>> treeDatas, CounterContainer cc) {
assert treeDatas != null;
assert cc != null;
TreeData<T> treeData = treeDatas.get(cc.getCounter());
TreeNode<T> node = new TreeNode<T>(null, treeData.getData(), null);
if (treeData.isLeaf()) return node;
if (treeData.getLeft()) {
cc.increment();
node.left = preOrderDeserialize(treeDatas, cc);
}
if (treeData.getRight()) {
cc.increment();
node.right = preOrderDeserialize(treeDatas, cc);
}
return node;
}
public List<T> preOrderIterator () {
final List<T> preOrderList = new ArrayList<T>();
if (root == null) throw new NoSuchElementException("The root should be non-null");
preOrder(root, preOrderList);
return preOrderList;
}
private void preOrder (TreeNode<T> node, List<T> preOrderList) {
assert preOrderList != null;
if (node != null) {
preOrderList.add(node.item);
preOrder(node.left, preOrderList);
preOrder(node.right, preOrderList);
}
}
public static void main(String[] args) {
/**
* 1
* 2 3
* 4 n 6 n
*/
Integer[] arr2 = { 1, 2, 3, 4, null, 6 };
SerializeDeserializeBinarytree<Integer> sdbt = new SerializeDeserializeBinarytree<Integer>(Arrays.asList(arr2));
for (TreeData<Integer> treeData : sdbt.serialize()) {
System.out.print(treeData.getData() + ":");
}
System.out.println();
sdbt.deserialize(sdbt.serialize());
for (Integer node : sdbt.preOrderIterator()) {
System.out.print(node + ":");
}
}
}
Solution
If your goal is to serialize the tree, then you want to repeatedly append node representations to a StringBuilder or write them to an OutputStream. For space efficiency, it would be better to do so a node at a time, rather than to build up the entire list.
Therefore, instead of using a List<TreeData<T>> as the intermediate data structure, you should create an PreOrderIterator<TreeData<T>>, InOrderIterator<TreeData<T>>, etc.
A minor bug: You get an IndexOutOfBoundsException for an empty list in SerializeDeserializeBinarytree.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.