Wednesday 3 August 2011

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

No comments:

Post a Comment