# Binary Tree Rebuilder

• binary • code • qt • personal • tree • binary-tree • visit • it • solution • english • rebuilder
• 767 words

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? ;)