# Binary Tree Rebuilder

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*

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**.

### The solution

Well, after the crappiest algorithmic explanation I have ever written, here it comes the code.

This time it’s not pure C: I wanted to use the beautiful Qt Framework that I’m using since July/August 2009 for work. I will attach the code full code into a ZIP file; here I report at least the core algorithm:

```
#include "TreeRebuilder.h"
#include <QDebug>
TreeRebuilder::TreeRebuilder() { }
TreeNode *TreeRebuilder::rebuild(QVector<TREE_NODE_VAL_TYPE> *preOrderVisit, QVector<TREE_NODE_VAL_TYPE> *inOrderVisit) {
reset();
m_preOrderVisit = preOrderVisit;
m_inOrderVisit = inOrderVisit;
mapNodePosInInOrderVisit();
return doRebuild(0, m_inOrderVisit->size() - 1);
}
void TreeRebuilder::mapNodePosInInOrderVisit() {
if ( !m_inOrderVisit ) {
qCritical() << "InOrder Visit not provided";
}
// Memorize the Position in the InOrder Visit of every element for quick-lookup
for (qint32 i = 0; i < m_inOrderVisit->size(); ++i) {
m_nodePosInInOrderVisit.insert(m_inOrderVisit->at(i), i);
}
}
TreeNode *TreeRebuilder::doRebuild(const qint32 &inOrderLeftLimit, const qint32 &inOrderRightLimit) {
TreeNode *newNode = new TreeNode;
qDebug() << "[Node:\t" << m_preOrderVisit->at( m_currRootInPreOrderVisit ) << "]";
newNode->val = m_preOrderVisit->at( m_currRootInPreOrderVisit++ ); // Post-increment used to select the next New Node value, taken from the PreOrder Visit
if ( inOrderLeftLimit < inOrderRightLimit ) {
// If the current Node Value is not the first in the InOrderVisit current range, means there is a Left Child
if ( m_nodePosInInOrderVisit.value(newNode->val) > inOrderLeftLimit ) {
qDebug() << " Found Left Child";
newNode->leftChild = doRebuild(inOrderLeftLimit, m_nodePosInInOrderVisit.value(newNode->val) -1);
}
// If the current Node Value is not the last in the InOrderVisit current range, means there is a Right Child
if ( m_nodePosInInOrderVisit.value(newNode->val) < inOrderRightLimit ) {
qDebug() << " Found Right Child";
newNode->rightChild = doRebuild(m_nodePosInInOrderVisit.value(newNode->val) + 1, inOrderRightLimit);
}
}
qDebug() << "[/Node:\t" << newNode->val << "]";
return newNode;
}
void TreeRebuilder::reset() {
m_currRootInPreOrderVisit = 0;
m_preOrderVisit = NULL;
m_inOrderVisit = NULL;
m_nodePosInInOrderVisit.clear();
}
QVector<TREE_NODE_VAL_TYPE> TreeRebuilder::generateInOrderVisit(TreeNode * const root) {
QVector<TREE_NODE_VAL_TYPE> result;
TreeRebuilder::doGenerateInOrderVisit(root, &result);
return result;
}
void TreeRebuilder::doGenerateInOrderVisit(TreeNode * const root, QVector<TREE_NODE_VAL_TYPE> *result) {
if ( NULL != root ) {
doGenerateInOrderVisit(root->leftChild, result);
result->append(root->val);
doGenerateInOrderVisit(root->rightChild, result);
}
}
QVector<TREE_NODE_VAL_TYPE> TreeRebuilder::generatePreOrderVisit(TreeNode * const root) {
QVector<TREE_NODE_VAL_TYPE> result;
TreeRebuilder::doGeneratePreOrderVisit(root, &result);
return result;
}
void TreeRebuilder::doGeneratePreOrderVisit(TreeNode * const root, QVector<TREE_NODE_VAL_TYPE> *result) {
if ( NULL != root ) {
result->append(root->val);
doGeneratePreOrderVisit(root->leftChild, result);
doGeneratePreOrderVisit(root->rightChild, result);
}
}
```

Mmm, I can see that the code doesn’t look very clear in here. Well, again, the code is downloadable from: TreeRebuilder.tar.gz

For Qt experts: yes, I’m using just the build-mechanism of Qt and the containers. All the rest is just plain C++. But using Signals and Slots for this would have been a massive overkill, don’t you think? ;)