Google Interview Question: Given the pre-order and in-or... | Glassdoor

## Interview Question

Software Engineer Interview London, England (UK)

# Given the pre-order and in-order traversing result of a

binary tree, write a function to rebuild the tree.
Tags:
algorithm

0

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.

alexb_sf on Jun 24, 2010
0

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&amp; PRE, const std::vector&amp; IN) {
node * r = new node(0,PRE); // root
node * v = r; // what we want to return
bool l = PRE != IN; // do I go left?
std::set path; // ancestors
path.insert(PRE);

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

r = l ? r-&gt;_left = n : r-&gt;_right = n;
l = true; // revert to left
if (PRE[p] == IN[i]) { // must go right or up
++i;
while(i _v);
r = r-&gt;_up;
if (r-&gt;_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".

magyar on Jul 4, 2010
0

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;

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 &amp;&amp; leftPreOrderS.length != 0)
root.left = rebuildTree(leftInOrderS, leftPreOrderS);
if (rightInOrderS.length != 0 &amp;&amp; rightPreOrderS.length != 0)
root.right = rebuildTree(rightInOrderS, rightPreOrderS);

return root;
}

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

}

Stefan T on Jul 11, 2010
0

package datastructures.trees;

public class BuildTreeInorderPreorder {

public static void buildTree(int[] inorder, int[] preorder)
{
TreeNode root = createNode(preorder,inorder,0,preorder.length-1,0,inorder.length - 1);
printPostOrder(root);
}

private static TreeNode createNode(int[] preorder, int[] inorder, int ps, int pe, int is, int ie)
{
if(ps &gt; pe || is &gt; ie)
{
return null;
}

TreeNode newNode = new TreeNode(preorder[ps]);
int i;
for(i = is; i &lt;= ie; i++)
{
if(preorder[ps] == inorder[i])
{
break;
}
}
newNode.left = createNode(preorder, inorder, ps + 1, ps + i - is, is, i - 1);
newNode.right = createNode(preorder, inorder, ps + i - is + 1, pe, i + 1, ie);
return newNode;
}

private static void printPostOrder(TreeNode node)
{
if(node == null)
{
return;
}

printPostOrder(node.left);
printPostOrder(node.right);
System.out.print(node.x + "");
}

public static void main(String[] args) {

int[] preorder = {1,2,4,7,8,5,3,6,9,10,11,12};
int[] inorder = {7,4,8,2,5,1,3,9,6,10,12,11};
buildTree(inorder,preorder);
}

}

class TreeNode
{
int x;
TreeNode left, right;

public TreeNode(int x)
{
this.x = x;
}
}

Victor on Jan 18, 2011
0

Here is a compact solution using recursion. Assume your pre-ordering is given in "pre", and in-ordering is given in "in", in the form of integers from 1 to n, representing nodes. "p" is an indicator showing which of the pre-order nodes we're currently procesing, and "ind" is used to quickly find where a node is in "in".

class Node
{
int value=-1;
Node left=null, right=null;
public Node(int val){value=val;}
public Node(int val, Node l, Node r){value=val;left=l;right=r;}
}

public class Rebuild
{
int[] pre, in,ind;
int p=-1;
public Node reconstruct(int st, int ed)
{
p++; //go to next root
if(st==ed)return new Node(pre[p]);
Node lr=reconstruct(st,ind[p]-1);
Node rr=reconstruct(ind[p]+1,ed);
return new Node(pre[p],lr,rr);
}
public static void main(String[] args)
{
//input "pre" and "in" however you want, initialise ind
for(int i=0;i

Lenny on Sep 12, 2014