How to Serialize Binary Tree

Question

I went to an interview today where I was asked to serialize a binary tree. I implemented an array-based approach where the children of node i (numbering in level-order traversal) were at the 2*i index for the left child and 2*i + 1 for the right child. The interviewer seemed more or less pleased, but I'm wondering what serialize means exactly? Does it specifically pertain to flattening the tree for writing to disk, or would serializing a tree also include just turning the tree into a linked list, say. Also, how would we go about flattening the tree into a (doubly) linked list, and then reconstructing it? Can you recreate the exact structure of the tree from the linked list?

Answer 1

All those articles talk mostly about the serialization part. The deserialization part is slightly tricky to do in one pass.

I have implemented an efficient solution for deserialization too.

Problem: Serialize and Deserialize a binary tree containing positive numbers.

Serialization part:

1. Use 0 to represent null.
2. Serialize to list of integers using preorder traversal.

Deserialization part:

1. Takes in list of integers and uses recursive helper method for deserialization.
2. Recursive deserializer returns a pair (BTNode node, int nextIndexToRead) where node is tree node constructed so far, and nextIndexToRead is position of next number to be read in the serialized list of numbers.

Below is the code in Java:

public final class BinaryTreeSerializer {     public static List<Integer> Serialize(BTNode root)     {         List<Integer> serializedNums = new ArrayList<Integer>();          SerializeRecursively(root, serializedNums);          return serializedNums;     }      private static void SerializeRecursively(BTNode node, List<Integer> nums)     {         if (node == null)         {             nums.add(0);             return;         }          nums.add(node.data);         SerializeRecursively(node.left, nums);         SerializeRecursively(node.right, nums);     }      public static BTNode Deserialize(List<Integer> serializedNums)     {         Pair pair = DeserializeRecursively(serializedNums, 0);          return pair.node;     }      private static Pair DeserializeRecursively(List<Integer> serializedNums, int start)     {                 int num = serializedNums.get(start);          if (num == 0)         {             return new Pair(null, start + 1);         }          BTNode node = new BTNode(num);          Pair p1 = DeserializeRecursively(serializedNums, start + 1);         node.left = p1.node;          Pair p2 = DeserializeRecursively(serializedNums, p1.startIndex);         node.right = p2.node;          return new Pair(node, p2.startIndex);     }      private static final class Pair     {         BTNode node;         int startIndex;          private Pair(BTNode node, int index)         {             this.node = node;             this.startIndex = index;         }     } }  public class BTNode  {     public int data;     public BTNode left;     public BTNode right;      public BTNode(int data)     {         this.data = data;     } } 

Answer 2

Using pre order traversal, serialize Binary tree. Use the same pre order traversal to deserialize tree. Be careful about the edge cases. Here null nodes are represented by "#"

public static String serialize(TreeNode root){             StringBuilder sb = new StringBuilder();             serialize(root, sb);             return sb.toString();         }      private static void serialize(TreeNode node, StringBuilder sb){         if (node == null) {             sb.append("# ");         } else {             sb.append(node.val + " ");             serialize(node.left, sb);             serialize(node.right, sb);         }     }      public static TreeNode deserialize(String s){         if (s == null || s.length() == 0) return null;         StringTokenizer st = new StringTokenizer(s, " ");         return deserialize(st);     }      private static TreeNode deserialize(StringTokenizer st){         if (!st.hasMoreTokens())             return null;         String val = st.nextToken();         if (val.equals("#"))             return null;         TreeNode root = new TreeNode(Integer.parseInt(val));         root.left = deserialize(st);         root.right = deserialize(st);         return root;     }