Serialize and Deserialize a Binary Tree

Given a binary tree, how can you serialize and deserialize it? Serialization: Storing a given tree in a file or in an array. Deserialization: Reverse of serialization. Serialization is done using pre-order traversal - A pre-order traversal array is created by visiting the tree in Root Node-Left subtree-Right subtree style in recursive manner. We write a special marker ‘-1’ whenever a null node is encountered. -------------- For Deserialization, following algorithm is used - int index = 0; Node deserialize(ArrayList array) { if (index == array.size() || array.get(index) == -1) { index += 1; return null; } Node root = new Node(array.get(index)); index += 1; root.left = deserialize(array); root.right = deserialize(array); return root; } Time Complexity: O(n) Space Complexity: O(n) Website: http://www.ideserve.co.in Facebook:   / ideserve.co.in