tryingout: 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

tryingout