Imagine you have a Binary Tree, with those characteristics:

* Nodes do not respect any order relation - In other words: it's <strong>not</strong> a [Binary Search Tree](http://en.wikipedia.org/wiki/Binary_search_tree) of any kind

* Every node appears <em>once and only once</em> 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.

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

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