Wednesday 3 August 2011

Deserializing Binary Tree from inorder and preorder traversal

Suppose we are given preorder and inorder tree traversal data, is it possible to recreate original Binary tree? Yes it is.

   1:  static Node DeserializePreInorder(int[] preorder, int[] inorder)
   2:  {
   3:      int[] mapping = new int[inorder.Length];
   4:      for (int i = 0; i < inorder.Length; i++)
   5:      {
   6:          mapping[inorder[i]] = i;
   7:      }
   8:      int start = 0;
   9:      return DeserializePreInorder(preorder, inorder, mapping, 0, inorder.Length, ref start);
  10:  }
  11:   
  12:  static Node DeserializePreInorder(int[] preorder, int[] inorder, int[] mapping, int low, int high, ref int readPointer)
  13:  {
  14:      if (low == high)
  15:      {
  16:          return null;
  17:      }
  18:      Node root = new Node { data = preorder[readPointer++] };
  19:      int dividerIndex = mapping[root.data];
  20:      root.left = DeserializePreInorder(preorder, inorder, mapping, low, dividerIndex, ref readPointer);
  21:      root.right = DeserializePreInorder(preorder, inorder, mapping, dividerIndex + 1, high, ref readPointer);
  22:      return root;
  23:  }
 
For detailed discussion see here

No comments:

Post a Comment