Serializing/deserializing binary tree in most space-efficient way

Question

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 + ":");
 }
 }
}

• 200_success: "Serialization" usually means to turn an object into a machine-readable string representation or byte stream. Do you mean "traversal" and "reconstruction"?
• JavaDeveloper: Yes, well, my code is one step short of it. my missing step would be to use object output stream to convert list into byte stream

Answer 1

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.

Answer 2

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.