1
\$\begingroup\$

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 + ":");
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ "Serialization" usually means to turn an object into a machine-readable string representation or byte stream. Do you mean "traversal" and "reconstruction"? \$\endgroup\$ – 200_success Dec 26 '13 at 12:24
  • \$\begingroup\$ 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 \$\endgroup\$ – JavaDeveloper Dec 26 '13 at 18:55
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\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.