Binary Tree Serialization and Deserialization

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.

There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.

hint:

http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/

  1 public class BTSerialize {
  2     class TreeNode {
  3         char val;
  4         TreeNode left, right;
  5         public TreeNode(char val) {
  6             this.val = val;
  7         }
  8     }
  9     public String serialization(TreeNode root) {
 10         StringBuilder str = new StringBuilder();
 11         if (root == null)
 12             return str.toString();
 13         TreeNode cur;
 14         Stack<TreeNode> stack = new Stack<TreeNode>();
 15         stack.push(root);
 16         while (!stack.isEmpty()) {
 17             cur = stack.pop();
 18             if (cur.val == '#') {
 19                 str.append("#,");
 20                 continue;
 21             }
 22             str.append(cur.val);
 23             if (cur.left != null || cur.right != null) {
 24                 str.append("|");
 25                 if (cur.right != null) {
 26                     stack.push(cur.right);
 27                 } else {
 28                     stack.push(new TreeNode('#'));
 29                 }
 30                 if (cur.left != null) {
 31                     stack.push(cur.left);
 32                 } else {
 33                     stack.push(new TreeNode('#'));
 34                 }
 35             }
 36             str.append(",");
 37         }
 38         return str.toString();
 39     }
 40     
 41     int idx = 0;
 42     public TreeNode deserialize(String data) {
 43         if (data == null || data.length() == 0) return null;
 44         String[] strs = data.split(",");
 45         TreeNode root = null;
 46         idx = 0;
 47         root = helpRead(root, strs);
 48         return root;
 49     }
 50     private TreeNode helpRead(TreeNode cur, String[] strs) {
 51         if (idx >= strs.length) return null;
 52         if (strs[idx].equals("#")) {
 53             idx++;
 54             return null;
 55         } else {
 56             int len = strs[idx].length();
 57             if (strs[idx].charAt(len-1) == '|') {
 58                 char val = strs[idx].charAt(0);
 59                 cur = new TreeNode(val);
 60                 idx++;
 61                 cur.left = helpRead(cur.left, strs);
 62                 cur.right = helpRead(cur.right, strs);
 63                 return cur;
 64             } else {
 65                 char val = strs[idx].charAt(0);
 66                 cur = new TreeNode(val);
 67                 idx++;
 68                 return cur;
 69             }
 70         }
 71     }
 72     
 73     public static void main(String[] args) {
 74         BTSerialize sol = new BTSerialize();
 75         TreeNode node0 = sol.new TreeNode('A');
 76         TreeNode node1 = sol.new TreeNode('B');
 77         TreeNode node2 = sol.new TreeNode('C');
 78         TreeNode node3 = sol.new TreeNode('D');
 79         TreeNode node4 = sol.new TreeNode('E');
 80         TreeNode node5 = sol.new TreeNode('F');
 81         TreeNode node6 = sol.new TreeNode('G');
 82         node0.left = node1; node0.right = node2;
 83         node1.left = node3; node1.right = node4;
 84         node2.left = node5;
 85         node3.right = node6;
 86         String str = sol.serialization(node0);
 87         System.out.println(str);
 88         TreeNode root = sol.deserialize(str), cur;
 89         Stack<TreeNode> stack = new Stack<TreeNode>();
 90         stack.push(root);
 91         while(!stack.isEmpty()) {
 92             cur = stack.pop();
 93             System.out.print(cur.val+", ");
 94             if (cur.right != null) stack.push(cur.right);
 95             if (cur.left != null) stack.push(cur.left);
 96         }
 97     }
 98 }
 99 /*
100              A
101          /       
102         B         C
103       /         /  
104      D     E    F    
105                    
106        G           
107 */