American Heritage

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them in graphic form, he records them in the more linear ‘tree in-order’ and ‘tree pre-order’ notations.

Your job is to create the ‘tree post-order’ notation of a cow’s heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can frequently reconstruct a tree from any two of the ordered traversals.) Obviously, the trees will have no more than 26 nodes.

Here is a graphical representation of the tree used in the sample input and output:

      C
    /   \
   /     \
  B       G
 / \     /
A   D   H
   / \
  E   F

The in-order traversal of this tree prints the left sub-tree, the root, and the right sub-tree.

The pre-order traversal of this tree prints the root, the left sub-tree, and the right sub-tree.

The post-order traversal of this tree print the left sub-tree, the right sub-tree, and the root.

PROGRAM NAME: heritage

INPUT FORMAT

Line 1:	The in-order representation of a tree.
Line 2:	The pre-order representation of that same tree.

SAMPLE INPUT (file heritage.in)

ABEDFCHG CBADEFGH

OUTPUT FORMAT

A single line with the post-order representation of the tree.

SAMPLE OUTPUT (file heritage.out)

AEFDBHGC

CODE

Java

C++

Pascal

ANALYSIS

Russ Cox

Here’s one way: We use a recursive procedure to generate the actual binary tree. Once we have the tree, we execute a postorder traversal to print the node values.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

FILE *fout;

typedef struct Tree Tree;
struct Tree {
    int c;
    Tree *left;
    Tree *right;
};

Tree*
mktree(int c, Tree *left, Tree *right)
{
    Tree *t;
    t = (Tree*)malloc(sizeof *t);
    assert(t);
    t->c = c;
    t->left = left;
    t->right = right;
    return t;
}

/*
 * Pre and in point at strings of length len
 * that describe the same tree, in pre-order
 * and in-order traversals.  Return a
 * corresponding binary tree.
 */
Tree*
prein2tree(char *pre, char *in, int len)
{
    char *p;
    int llen, rlen;

    assert(strlen(pre)>=len && strlen(in)>=len);

    if(len == 0)
        return NULL;

    /*
     * The first character of the preorder traversal is the root.
     * If we find the root in the inorder traversal, then everything
     * to its left is on the left side, and everything to its right on the
     * right side.  Recur on both sides.
     */
    p = strchr(in, pre[0]);
    assert(p != NULL);
    assert(p-in < len);

    llen = p-in;
    rlen = len-llen-1;
    return mktree(pre[0], prein2tree(pre+1, in, llen), prein2tree(pre+1+llen, p+1, rlen));
}

void
postorder(Tree *t)
{
    if(t == NULL)
        return;
    postorder(t->left);
    postorder(t->right);
    fprintf(fout, "%c", t->c);
}

void
main(void)
{
    FILE *fin;
    char pre[50], in[50];

    fin = fopen("heritage.in", "r");
    fout = fopen("heritage.out", "w");
    assert(fin != NULL && fout != NULL);

    fscanf(fin, "%s %s", in, pre);
    postorder(prein2tree(pre, in, strlen(pre)));
    fprintf(fout, "\n");
    exit(0);
}

Greg Price

We don’t need to reconstruct the original tree explicitly for this problem. Instead, we use a recursive function that plucks the root from the start of the preorder traversal, uses it to divide the inorder traversal, calls itself recursively on the left and right subtrees, and outputs the root.

#include <fstream.h>
#include <string.h>

ifstream fin("heritage.in");
ofstream fout("heritage.out");

const short maxn = 26 + 2;

short len;
char in[maxn], pre[maxn];

void
makepost(short ina, short inb, short prea, short preb)
{
	char root;
	short rt_in;
	short lsize, rsize;

	if (ina == inb) // Null tree
		return;

	root = pre[prea];

	// Find root in inorder
	for (rt_in = ina; rt_in < inb; rt_in++)
		if (in[rt_in] == root)
			break;

	// Size of left-hand subtree
	lsize = rt_in -  ina;

	makepost(ina,     rt_in, prea+1,         prea+1 + lsize); // Left
subtree
	makepost(rt_in+1, inb,   prea+1 + lsize, preb); // Right subtree
	fout << root;
}

void
main()
{
	fin.getline(in , maxn);
	fin.getline(pre, maxn);

	len = strlen(in);

	makepost(0, len, 0, len);
	fout << endl;
}

Daniel Bundala

Here is a better and faster solution for problem “heritage”. I used standard recursive approach like solutions in analysis for the problem. But insert new element into the tree can be made faster. Because solutions in analysis in each recursive call are finding the position of inserting element in in-order representation of the tree. It is O(N) in O(N) calls worth case = O(N^2).

But what we can do is to precompute positions of elements in in-order representation and when we are inserting new elment e into the node n, e is in left subtree if and only if position_in_inorder[i] < position_in_inorder[n->value] otherwise element e is in right subtree.

Now inserting: O(1) in O(N) recursive call - worth case = O(N).

All algorithm is O(N^2) and before was O(N^3) - worth case. And O(N log N) now, before O(N^2) - average case; N = number of cows

My implementation (I’m using index into the array instead of pointer):

/*
LANG: C++
PROG: heritage
*/

#include <stdio.h>
#include <string.h>

FILE *in,*out;

char ino[200], preo[200];
int place[255];

struct NODE{
  int left, right;
  char name;
};

NODE node[200];
int count = 1;

//return true if who is before the value of node[n] in inorder; O(1)
bool isBefore(char who, int n){
  return place[who] < place[node[n].name];
};

void insert(char c, int where){
  if (isBefore(c, where)){ //in the left subtree
    if (node[where].left == -1){ //left subtree is empty
      node[count].left = node[count].right = -1;
      node[count].name = c;
      node[where].left = count++;
    } else {
      insert(c, node[where].left); //insert into the left subtree
    };
  } else { // in the right subtree
    if (node[where].right == -1){ //right subtree is empty
      node[count].left = node[count].right = -1;
      node[count].name = c;
      node[where].right = count++;
    } else {
      insert(c, node[where].right); //insert into the right subtree
    };
  };

};

void write(int kde){
  if (kde==-1) return;
  write(node[kde].left);
  write(node[kde].right);
  fprintf(out, "%c", node[kde].name);  
};

int main ()
{
  in=fopen("heritage.in","r");
  out = fopen ("heritage.out", "w");
  fgets(ino, 200, in);
  fgets(preo, 200, in);

  for (int i=0; i<strlen(ino); i++)
    place[ino[i]] = i;

  //insert root  
  node[0].left = node[0].right = -1;
  node[0].name = preo[0];

  //insert next element
  for (int i=1; i<strlen(ino) - 1; i++)
    insert(preo[i], 0);

  write(0); fprintf(out, "\n");

  fclose(in); fclose(out);
  return 0;
}

Nishant Redkar

India’s Nishant Redkar had a much simpler solution:

#include <fstream>
#include <string>
using namespace std;

ofstream out ("heritage.out");

void
recursex (string sin, string spre) {
    int i;
    if (sin.length() < 2) {
	out << sin;
	return;
    }
    for (i = 0; sin[i] != spre[0]; i++);
    recursex (sin.substr(0,i), spre.substr(1,i));
    recursex (sin.substr(i+1), spre.substr(i+1));
    out << spre[0];
}

int
main () {
    string sin, spre;
    ifstream in("heritage.in");
    in >> sin >> spre;
    recursex (sin, spre);
    out << endl;
    in.close();
    out.close();
    return 0;
}