Recreating Binary Tree from Inorder and Postorder traversal data

This is continuation of earlier post about recreating Binary tree from given Preorder and Inorder data. This blog post has C# code from recreating the tree from inorder and postorder. The algo here is almost same as previous one except we start reading the postOrder data from right hand side as right most node is post-order transversal is Root node.

   1:  static Node DeserializeInorderPost(int[] inorder, int[] postorder)

   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 readPtr = inorder.Length -1;

   9:      return DeserializeInorderPost(inorder, postorder, mapping, 0, inorder.Length, ref readPtr);

  10:  }

  11:   

  12:  static Node DeserializeInorderPost(int[] inorder, int[] postorder, int[] mapping, int start, int end, ref int readPtr)

  13:  {

  14:      if (end == start)

  15:      {

  16:          return null;

  17:      }

  18:   

  19:      Node root = new Node { data = postorder[readPtr--] };

  20:      int divider = mapping[root.data];

  21:      root.right = DeserializeInorderPost(inorder, postorder, mapping, divider+1, end, ref readPtr);

  22:      root.left = DeserializeInorderPost(inorder, postorder, mapping, start, divider, ref readPtr);

  23:      return root;

  24:  }

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