Today we look at using the Binary tree traversals to reconstruct the tree. We mentioned in yesterday's post that the preorder traversal and the inorder traversal can be used to determine the length of the left and right subtree of any node at the same time. Let us take a look at the solution now.

// Preorder A B C D E F
// Inorder   C B D A E F
// Build tree

Node BuildTree(char[] Preorder, char[] InOrder, int index = 0)
{
 Node root = new Node();
 root.data = PreOrder[index];
 root.left = null;
 root.right = null;

 int inIndex = Array,indexOf(InOrder, Preorder[index]);

 if ( index+1 < Preorder.Length &&
       IsLeftSubtree(Preorder[index+1], inOrder, inIndex) == true)
       root.left = BuildTree(Preorder, InOrder, index + 1);

 if ( inIndex+1 < InOrder.Length &&
       isPredecessor(InOrder[inIndex+1], Preorder, index) == false)
       root.right = BuildTree(Preorder, InOrder, Array.IndexOf(PreOrder, InOrder[inIndex + 1]));

 return root;
}

bool is Predecessor(char c, char[] Preorder, int index)
{
return Array.IndexOf(Preorder, c) < index;
}

bool isLeftSubtree(char c, char[] inOrder, int index)
{
Array.IndexOf(Inorder,c) < index;
}

or iteratively as follows:


Node  BuildTree(List<Node> pre, List<Node> in) // Node.left = null; Node.right = null;
{
for (int i = 0; i < pre.Length; i++)
{
int index = i;
int inIndex = Array,indexOf(in, pre[index]);
if ( index + 1 < pre.Length &&
     Array.IndexOf(in, pre[index+1]) < index)
   pre[i].left = pre[index+1];
if (inIndex+1 < in.Length &&
    Array.IndexOf(pre, in[inIndex+1]) >= index)
    pre[i].right = Array.IndexOf(pre, in[inIndex+1]);
}
return pre[0];
}