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