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
Answer

Interview Answer

5 Answers

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& PRE, const std::vector& 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 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 _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".

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[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");
    }

}

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 > pe || is > ie)
        {
            return null;
        }

        TreeNode newNode = new TreeNode(preorder[ps]);
        int i;
        for(i = is; i <= 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.