Imagine you have a Binary Tree, with those characteristics:

  • Nodes do not respect any order relation – In other words: it’s not a Binary Search Tree of any kind
  • Every node appears once and only once within the tree
A nice Binary Tree
A nice Binary Tree

Then, your little brother passes by your desk and, to upset you, deletes the tree from your computer memory/HD (yeah, I know, I’m pathetic at inventing hypothetical situations :-P ).

Fortunately though, you previously did a Pre-Order and an In-Order visit of your tree, and stored the result in an 2 nice array.

Can you rebuild the original tree structure out of this 2 array?

How are you going to rebuild it?

Yes, you can! (Sorry, I couldn’t resist). And it’s quite easy as well. What you have to do, is the following:

  • Take the first element of the PreOrder Array and use it as root of a new tree
  • Find the position of this New Node in the InOrder Array, scanning it from 0 to n-1 (n is the number of Nodes)
  • IF next element in the PreOrder Array is on the left of the New Node in the InOrder array: call RECURSIVELY this procedure, this time taking into account the portion of InOrder array that goes from 0 to the position of the New Node in the InOrder Array -1.
  • IF next element in the PreOrder Array is on the right of the New Node in the InOrder array: call RECURSIVELY this procedure, this time taking into account the portion of InOrder array that goes from the position of the New Node in the InOrder Array +1 to n-1.
  • Return the New Node

By the way, this doesn’t work. To fix it we should be more generic, specifying things a little bit better. Things like:

  • Every recursive calls takes into account a portion of the InOrder array; in the case of the first call it’s the entire array
  • There is going to be as much recursive calls as the number of elements in the PreOrder array

Of course, is a tree what we are talking about here: recursion is a MUST. More >