Gets binary tree from preorder and inorder traversal of nodes.

gistfile1.java

package com.timdumol.algos.graphs;
/** Computes the hierarchy of a binary tree given its
 * in-order and pre-order traversals. 
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class InOrderPreOrder {
	static int[] tree;

	static void solve(int[] pre, int[] in, int prel, int prer, int inl,
			int inr, int parent) {
		if (prel == prer || inl == inr)
			return;
		int root = pre[prel];
		tree[root] = parent;
		for (int i = 0; i < prer - prel; ++i) {
			if (in[inl + i] == root) {
				solve(pre, in, prel + i + 1, prer, inl + i + 1, inr, root);
				solve(pre, in, prel + 1, prel + i + 1, inl, inl + i + 1, root);
			}
		}

	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		PrintStream ps = out;
		String[] s = br.readLine().split(" ");
		int n = s.length;
		int[] pre = new int[n];
		int[] in = new int[n];

		for (int i = 0; i < n; ++i) {
			in[i] = Integer.parseInt(s[i]) - 1;
		}

		s = br.readLine().split(" ");
		for (int i = 0; i < n; ++i) {
			pre[i] = Integer.parseInt(s[i]) - 1;
		}
		tree = new int[n];
		solve(pre, in, 0, pre.length, 0, in.length, -1);
		for (int i = 0; i < tree.length; ++i) {
			ps.printf("%d's parent is %d\n", i + 1, tree[i] + 1);
		}
	}

}