Interview Question for Software Engineer at Google:

Here is the algorithm (I am too lazy to write the whole program).
Let's number the nodes of in-order traversing sequentially (1,2,3, etc.). Then take the list of nodes of pre-order traversing.
The first one is the root.
While their numbers (from in-order list) decreasing, connect them as left-hand children, one by one.
If the next number is greater, find the node with the max number (less than this one) and connect this one to it as right-hand child. Etc.

I think they meant any "binary tree" not a binary search tree; but ALL values must be different (imagine a tree with n 1's; it has a Catalan(n) configurations and the same pre- and in-order traversals). So here is a solution:

node* rec(const std::vector<int>& PRE, const std::vector<int>& IN) {
   node * r = new node(0,PRE[0]); // root
   node * v = r; // what we want to return
   bool l = PRE[0] != IN[0]; // do I go left?
   std::set<int> path; // ancestors
   path.insert(PRE[0]);

   for(int p=1, i=l ? 0 : 1; p!=(int)PRE.size(); ++p) {
      node * n = new node(r,PRE[p]);

      r = l ? r->_left = n : r->_right = n;
      l = true; // revert to left
      if (PRE[p] == IN[i]) { // must go right or up
         ++i;
         while(i < (int)(IN.size())) {
            if (path.find(IN[i]) == path.end()) { // not an ancestor
               l = false;
               break;
            } else {
               for(;;) {
                  path.erase(r->_v);
                  r = r->_up;
                  if (r->_v == IN[i]) {
                    ++i;
                    break;
                  }
               }
            }
         }
      }

      path.insert(PRE[p]);
   }
   return v;
}

The idea is that the pre-order is basically a depth-first search order, which is convenient to build the tree (it is always connected at every interim stage). The in-order is used to decide whether to move right or up. BTW, you can guess the definition of "node".

I have done something in Java. Maybe this might help:

import java.util.Arrays;
import java.util.TreeMap;

import javax.management.RuntimeErrorException;

public class BinaryTrees {

    public static class Node {
        Node right;
        Node left;
        char value;

        // preorder
// public String toString() {
// return (value + " ") + (this.left == null ? "" : this.left)
// + (this.right == null ? "" : this.right);
//
// }

        // in order
// public String toString() {
// return (this.left == null ? "" : this.left) +(value + " ") +
// (this.right == null ? "" : this.right);
//
// }

        // post order
        public String toString() {
            return (this.left == null ? "" : this.left) + ""
                    + (this.right == null ? "" : this.right) + (value + " ");

        }

    }

    private static final char[] preOrderStr = new char[] { 'u','f','A','C','M','h','s','9','6' };

    private static final char[] inOrderStr = new char[] { 'A','f','C','u','s','h','M','9','6' };

    public static void main(String... args) {
        BinaryTrees trees = new BinaryTrees();

        Node root = trees.rebuildTree(inOrderStr, preOrderStr);
        System.out.println(root);
    }

    public Node rebuildTree(char[] inOrderS, char[] preOrderS) {

        Node root = new Node();
        root.value = preOrderS[0];

        int index = getIndex(inOrderS, root.value);

        char[] leftInOrderS = new char[index];
        char[] rightInOrderS = new char[inOrderS.length - index - 1];

        char[] leftPreOrderS = new char[index];
        char[] rightPreOrderS = new char[preOrderS.length - index - 1];

        System.arraycopy(inOrderS, 0, leftInOrderS, 0, index);
        System.arraycopy(inOrderS, index + 1, rightInOrderS, 0, inOrderS.length
                - index - 1);

        System.arraycopy(preOrderS, 1, leftPreOrderS, 0, index);
        System.arraycopy(preOrderS, index+1, rightPreOrderS, 0, preOrderS.length
                - index -1);

        if (leftInOrderS.length != 0 && leftPreOrderS.length != 0)
            root.left = rebuildTree(leftInOrderS, leftPreOrderS);
        if (rightInOrderS.length != 0 && rightPreOrderS.length != 0)
            root.right = rebuildTree(rightInOrderS, rightPreOrderS);

        return root;
    }

    public int getIndex(char[] chars, char ch) {
        for (int i = 0; i < chars.length; i++)
            if (ch == chars[i])
                return i;
        throw new RuntimeException("No char " + ch + " in the vector");
    }

}