Construct Binary Tree From Inorder and Preorder/Postorder Traversal

/*

 http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

 Given preorder and inorder traversal of a tree, construct the binary tree.

 */

/* This is a problem we found on leetcode. It requires good understanding of the tree structure to solve this problem. Above is the link to the original post in which it contains detailed explanation for the approach. However, the code provided in the post does not work properly in my IDE (Xcode 4.4.1). I revised the solution so that it works fine now. J */

/* First we need to know how in-order, pre-order and post-order traversal work. Here is the implementation. */

#include <iostream>

#include <map>

using namespace std;

struct node{

    node(int);

    node * left;

    node * right;

    int value;

};

node::node(int value) {

    this->value = value; this->left = this->right = nullptr;

}

void print(node * n) {

    cout << n->value << " ";

}

void inorder(node * n) {

    if (n == nullptr) {

        return;

    }

    inorder(n->left);

    print(n);

    inorder(n->right);

}

void preorder(node * n) {

    if (n == nullptr) {

        return;

    }

    print(n);

    preorder(n->left);

    preorder(n->right);

}

void postorder(node * n) {

    if (n == nullptr) {

        return;

    }

    postorder(n->left);

    postorder(n->right);

    print(n);

}

/* Now it’s the imlpementation of the tree reconstruction.

 I only did for inorder+preorder, while inorder+postorder is quite similar to this. */

static map<int, int> value2index; // a fast lookup for inorder's element to its index

void mapToIndices(int inorder[], int len) {

    for (int i = 0; i < len; i++) {

        value2index[inorder[i]] = i;

    }

}

// a,b are start and end index of inorder array, c, d are start and end index of preorder array

node * buildInorderPreorder(int in[], int a, int b, int pre[], int c, int d) {

    if (b < a || d < c) {

        return nullptr;

    }

    int rootVal = pre[c];

    int rootPos = value2index[rootVal];

    node *root = new node(rootVal);

    root->left = buildInorderPreorder(in, a, rootPos-1, pre, c+1, c+rootPos-a);

    root->right = buildInorderPreorder(in, rootPos+1, b, pre, c+rootPos-a+1, d);

    return root;

}

void cleantree(node * n){

    if (n == nullptr) {

        return;

    }

    cleantree(n->left);

    cleantree(n->right);

    delete n;

}

int main(int argc, const char * argv[])

{

    node one(1), two(2), three(3), four(4), five(5), six(6), seven(7);

    two.left = &one; two.right = &three;

    six.left = &five; six.right = &seven;

    four.left = &two; four.right = &six;

    node * tree = &four;

    cout << "inorder:   ";

    inorder(tree);

    cout << endl << "preorder:  ";

    preorder(tree);

    cout << endl << "postorder: ";

    postorder(tree);

    cout << endl;

    int in[] = {1, 2, 3, 4, 5, 6, 7};

    int pre[] = {4, 2, 1, 3, 6, 5, 7};

    mapToIndices(in, 7);

    node * tree1 = buildInorderPreorder(in, 0, 6, pre, 0, 6);

    inorder(tree1);

    cleantree(tree1);

    return 0;

}