Google Interview Question Software Engineers
Country: UK
Interview Type: In-Person
Yes, but how do you know which node goes on the left and right of a given parent? How about single long branches on the left or right in unbalanced trees ? Can you describe how your algorithm would tackle those scenarios?
@eng.ahmed.moustafa - I can't remember exactly anymore but I think I asked the same question and got reply to assume the elements are distinct. It's a good question though.
@guilhebl - the trick is that the order of the listing determines that - elements in the "before" lists go to the left, elements in the "after" lists go to the right (i.e. it was still assumed that the in/pre-order take the left child first)
With preorder, we know the first element would be the head, and the second element would be the left child. When we find this head in the inorder, we will know that the node directly to the right of the head in inorder will be the right subchild.
Python implementation of the idea:
from collections import defaultdict
def build_tree(preorder, inorder, adj_list):
node = preorder[0]
node_id = inorder.index(node)
left_inorder = inorder[0:node_id]
right_inorder = inorder[(node_id+1):]
left_preorder = preorder[1:(len(left_inorder)+1)]
right_preorder = preorder[len(left_inorder)+1:]
if len(left_preorder) != 0:
adj_list[node].append(left_preorder[0])
else:
adj_list[node].append(None)
if len(right_preorder) != 0:
adj_list[node].append(right_preorder[0])
else:
adj_list[node].append(None)
if len(left_preorder) != 0:
build_tree(left_preorder, left_inorder, adj_list)
if len(right_preorder) != 0:
build_tree(right_preorder, right_inorder, adj_list)
return
#main
preorder = [2,7,3,6,8,11,5,9,4]
inorder = [3,7,8,6,11,2,5,4,9]
adj_list = defaultdict(list)
build_tree(preorder, inorder, adj_list)
print adj_list
def reconstruct (preorder, inorder):
l = len (preorder)
assert l == len (inorder)
if l == 0:
return None
value = preorder[0]
left_size = inorder.index (value)
left = reconstruct (preorder[1:left_size + 1], inorder[0:left_size])
right = reconstruct (preorder[left_size + 1:], inorder [left_size + 1:])
return Node (value, left, right)
import java.io.*;
import java.util.*;
class Tree{
int key;
Tree right;
Tree left;
Tree(int key){
this.key=key;
this.right=null;
this.left=null;
}
}
public class TreeForm{
static int[] inorder;
static int[] preorder;
public static void main(String[] args){
try{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] inorderStr=br.readLine().split(" ");
inorder=new int[inorderStr.length];
String[] preorderStr=br.readLine().split(" ");
preorder=new int[preorderStr.length];
for(int i=0;i<inorder.length;i++)inorder[i]=Integer.parseInt(inorderStr[i]);
for(int i=0;i<inorder.length;i++)preorder[i]=Integer.parseInt(preorderStr[i]);
Tree tr=makeTree(inorder,0,inorder.length-1);
// if(tr!=null)
postorderTree(tr);
//else{
//System.out.println("sry No Tree");
//}
}catch(IOException e){
System.out.println(e);
}
}
static int p=-1;
public static Tree makeTree(int[] a, int i,int j)
{++p;
if(i<a.length && p<a.length){
if(i==j){
return new Tree(a[i]);
}
else{
int index=find(preorder[p]);
Tree root=new Tree(a[index]);
root.left=makeTree(a, i, index-1);
root.right=makeTree(a,index+1,j);
// p++;
return root;
}
}else{
return null;
}
}
public static int find(int key){
int k=-1;
for(int i=0;i<inorder.length;i++){
if(inorder[i]==key){
k=i;
break;
}
}
return k;
}
public static void postorderTree(Tree t){
if(t!=null){
postorderTree(t.left);
postorderTree(t.right);
System.out.println(t.key);
//inorderTree(t.right);
}
}
}
Here's my solution in C#, I look at my code then I look at Mr Python's 10 line solution and I feel sick. Damn, that's just showing off! :)
public class Printouts
{
public Node Reconstruct(string inOrder, string preOrder)
{
if (inOrder.Length != preOrder.Length)
throw new UnexpectedStateException(“Different lengths”);
if (inOrder.Length == 0)
return null;
string rootValue = preOrder.Substring(0,1);
var root = new Node(rootValue);
int rootIndex = inOrder.IndexOf(rootValue);
if (rootIndex < 0)
throw new UnexpectedStateException(string.Format(“{0} must be present in both in-order and pre-order”, rootValue));
string leftInOrder = inOrder.Substring(0, rootIndex);
string rightInOrder = inOrder.Substring(rootIndex + 1, inOrder.Length - (rootIndex + 1));
string leftPreOrder = preOrder.Substring(1,leftInOrder.Length);
string rightPreOrder = preOrder.Substring(1 + leftInOrder.Length);
root.Left = Reconstruct(leftInOrder, leftPreOrder);
root.Right = Reconstruct(rightInOrder, rightPreOrder);
return root;
}
}
Here's my C++ code
class Node
{
public:
Node * lChild, * rChild;
int value;
Node(int val):value{val} {};
};
Node * reconstructTree(int * preorder, int * inorder, int length)
{
if(length <= 0)
{
return nullptr;
}
int * prePtr = preorder;
int * inPtr = inorder;
int rootVal = *prePtr;
int subLength = 0;
int * preSubSt = prePtr + 1;
while(*inPtr != rootVal)
{
prePtr++; inPtr++; subLength++;
}
Node * root = new Node(rootVal);
root->lChild = reconstructTree(preSubSt, inorder, subLength);
root->rChild = reconstructTree(prePtr + 1, inPtr + 1, length - subLength - 1);
return root;
};
public static int[] reBuildTree(int[] preOrder,int[] inOrder)
{
int count=preOrder.length*2;
int[] tree=new int[count];
int i=0;
buildTree(preOrder, inOrder, tree, i);
return tree;
}
public static void buildTree(int[]preOrder,int[]inOrder,int[]tree,int i)
{
if(preOrder.length>0)
{
int root=preOrder[0];
tree[i]=root;
//assume there are not duplicate elements in the tree
int j=0;
while(inOrder[j]!=root && j<inOrder.length)
j++;
if(j>0)
{
int[] inOrderLeft=new int[j];
int[] preOrderLeft=new int[j];
int z=0;
//All the elements to the left of the root are the left subtree
while(inOrder[z]!=root && z<inOrder.length)
{
inOrderLeft[z]=inOrder[z];
preOrderLeft[z]=preOrder[z+1];
z++;
}
buildTree(preOrderLeft, inOrderLeft, tree, 2*i+1);
}
if(j<inOrder.length)
{
int[] inOrderRight=new int[inOrder.length-(j+1)];
int[] preOrderRight=new int[preOrder.length-(j+1)];
j++;
int k=0;
//All the elements to the right of the root are the right subtree
while(j<inOrder.length)
{
inOrderRight[k]=inOrder[j];
preOrderRight[k]=preOrder[j];
j++;
k++;
}
buildTree(preOrderRight, inOrderRight, tree, 2*i+2);
}
}
return;
}
Here is another solution. It uses a HashMap to map the element to the position in the in-order array. And then iterates through the pre-order array, dividing the in-order array into halves recursively. Since hashmap is used to lookup the position in the in-order array, it takes a constant time for the find operation.
public class TreeExercise {
private HashMap<Integer, Integer> inOrderElementPositionMap = new HashMap<Integer, Integer>();
private int preOrderPointer = 0;
public BinaryTree<Integer> buildTree(String inOrderPrint, String preOrderPrint) {
String[] inOrderStrings = inOrderPrint.split(" ");
String[] preOrderStrings = preOrderPrint.split(" ");
int[] inOrderNumbers = new int[inOrderStrings.length];
int[] preOrderNumbers = new int[inOrderStrings.length];
for (int i=0 ; i<inOrderStrings.length ; i++) {
inOrderNumbers[i] = Integer.parseInt(inOrderStrings[i]);
preOrderNumbers[i] = Integer.parseInt(preOrderStrings[i]);
}
//load in-order array into a map
loadInOrderElementPositionMap(inOrderNumbers);
//build the tree
Node<Integer> root = buildTree(inOrderNumbers, 0, inOrderNumbers.length-1, preOrderNumbers);
return new BinaryTree<Integer>(root);
}
/**
* load the in-order array into a hashmap mapping the element to position in the array
* @param inOrderNumbers
*/
private void loadInOrderElementPositionMap(int[] inOrderNumbers) {
for (int i = 0 ; i < inOrderNumbers.length ; i++) {
inOrderElementPositionMap.put(inOrderNumbers[i], i);
}
}
/**
*
* @param inOrder - inorder array
* @param start - start element in the inorder array for this method execution
* @param end - end element in the inorder array for this method execution
* @param preOrder - preorder array
* @return
*/
private Node<Integer> buildTree(int[] inOrder, int start, int end, int[] preOrder) {
Node<Integer> node = null;
if (start <= end && preOrderPointer < preOrder.length) {
int element = preOrder[preOrderPointer];
int position = inOrderElementPositionMap.get(element);
if (position >= start && position <= end) {
//build the Node for this element if we find a match
node = new Node<Integer>(element);
//increment the iterating pointer only where there is a match
preOrderPointer++;
//now divide the array into two subtrees, and build nodes for each of them recursively
node.left = buildTree(inOrder, 0, position-1, preOrder);
node.right = buildTree(inOrder, position+1, end, preOrder);
}
}
return node;
}
public static void main(String[] args) {
Node<Integer> root = new Node<Integer>(10);
Node<Integer> node4 = new Node<Integer>(4);
root.left = node4;
Node<Integer> node5 = new Node<Integer>(5);
root.right = node5;
Node<Integer> node6 = new Node<Integer>(6);
Node<Integer> node9 = new Node<Integer>(9);
node4.left = node6;
node4.right = node9;
Node<Integer> node11 = new Node<Integer>(11);
Node<Integer> node3 = new Node<Integer>(3);
node5.left = node11;
node5.right = node3;
Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node7 = new Node<Integer>(7);
node6.left = node1;
node9.right = node7;
BinaryTree<Integer> tree = new BinaryTree<Integer>(root);
System.out.print("InOrder : ");
tree.printInOrder();
System.out.println();
System.out.print("PreOrder : ");
tree.printPreOrder();
TreeExercise exercises = new TreeExercise();
System.out.println("\ncreating new tree...");
BinaryTree<Integer> newTree = exercises.buildTree("1 6 4 9 7 10 11 5 3", "10 4 6 1 9 7 5 11 3");
System.out.println("New Tree");
System.out.print("InOrder : ");
newTree.printInOrder();
System.out.println();
System.out.print("PreOrder : ");
newTree.printPreOrder();
}
}
This is another solution using the same idea, but uses a Hashmap initially to store the element to position in the in-order map to avoid calling find() everytime. This would anyway does not work if there are duplicate elements
public class TreeExercise {
private HashMap<Integer, Integer> inOrderElementPositionMap = new HashMap<Integer, Integer>();
private int preOrderPointer = 0;
public BinaryTree<Integer> buildTree(String inOrderPrint, String preOrderPrint) {
String[] inOrderStrings = inOrderPrint.split(" ");
String[] preOrderStrings = preOrderPrint.split(" ");
int[] inOrderNumbers = new int[inOrderStrings.length];
int[] preOrderNumbers = new int[inOrderStrings.length];
for (int i=0 ; i<inOrderStrings.length ; i++) {
inOrderNumbers[i] = Integer.parseInt(inOrderStrings[i]);
preOrderNumbers[i] = Integer.parseInt(preOrderStrings[i]);
}
//load in-order array into a map
loadInOrderElementPositionMap(inOrderNumbers);
//build the tree
Node<Integer> root = buildTree(inOrderNumbers, 0, inOrderNumbers.length-1, preOrderNumbers);
return new BinaryTree<Integer>(root);
}
/**
* load the in-order array into a hashmap mapping the element to position in the array
* @param inOrderNumbers
*/
private void loadInOrderElementPositionMap(int[] inOrderNumbers) {
for (int i = 0 ; i < inOrderNumbers.length ; i++) {
inOrderElementPositionMap.put(inOrderNumbers[i], i);
}
}
/**
*
* @param inOrder - inorder array
* @param start - start element in the inorder array for this method execution
* @param end - end element in the inorder array for this method execution
* @param preOrder - preorder array
* @return
*/
private Node<Integer> buildTree(int[] inOrder, int start, int end, int[] preOrder) {
Node<Integer> node = null;
if (start <= end && preOrderPointer < preOrder.length) {
int element = preOrder[preOrderPointer];
int position = inOrderElementPositionMap.get(element);
if (position >= start && position <= end) {
//build the Node for this element if we find a match
node = new Node<Integer>(element);
//increment the iterating pointer only where there is a match
preOrderPointer++;
//now divide the array into two subtrees, and build nodes for each of them recursively
node.left = buildTree(inOrder, 0, position-1, preOrder);
node.right = buildTree(inOrder, position+1, end, preOrder);
}
}
return node;
}
public static void main(String[] args) {
Node<Integer> root = new Node<Integer>(10);
Node<Integer> node4 = new Node<Integer>(4);
root.left = node4;
Node<Integer> node5 = new Node<Integer>(5);
root.right = node5;
Node<Integer> node6 = new Node<Integer>(6);
Node<Integer> node9 = new Node<Integer>(9);
node4.left = node6;
node4.right = node9;
Node<Integer> node11 = new Node<Integer>(11);
Node<Integer> node3 = new Node<Integer>(3);
node5.left = node11;
node5.right = node3;
Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node7 = new Node<Integer>(7);
node6.left = node1;
node9.right = node7;
BinaryTree<Integer> tree = new BinaryTree<Integer>(root);
System.out.print("InOrder : ");
tree.printInOrder();
System.out.println();
System.out.print("PreOrder : ");
tree.printPreOrder();
TreeExercise exercises = new TreeExercise();
System.out.println("\ncreating new tree...");
BinaryTree<Integer> newTree = exercises.buildTree("1 6 4 9 7 10 11 5 3", "10 4 6 1 9 7 5 11 3");
System.out.println("New Tree");
System.out.print("InOrder : ");
newTree.printInOrder();
System.out.println();
System.out.print("PreOrder : ");
newTree.printPreOrder();
}
}
public class TreeExercise {
private HashMap<Integer, Integer> inOrderElementPositionMap = new HashMap<Integer, Integer>();
private int preOrderPointer = 0;
public BinaryTree<Integer> buildTree(String inOrderPrint, String preOrderPrint) {
String[] inOrderStrings = inOrderPrint.split(" ");
String[] preOrderStrings = preOrderPrint.split(" ");
int[] inOrderNumbers = new int[inOrderStrings.length];
int[] preOrderNumbers = new int[inOrderStrings.length];
for (int i=0 ; i<inOrderStrings.length ; i++) {
inOrderNumbers[i] = Integer.parseInt(inOrderStrings[i]);
preOrderNumbers[i] = Integer.parseInt(preOrderStrings[i]);
}
//load in-order array into a map
loadInOrderElementPositionMap(inOrderNumbers);
//build the tree
Node<Integer> root = buildTree(inOrderNumbers, 0, inOrderNumbers.length-1, preOrderNumbers);
return new BinaryTree<Integer>(root);
}
/**
* load the in-order array into a hashmap mapping the element to position in the array
* @param inOrderNumbers
*/
private void loadInOrderElementPositionMap(int[] inOrderNumbers) {
for (int i = 0 ; i < inOrderNumbers.length ; i++) {
inOrderElementPositionMap.put(inOrderNumbers[i], i);
}
}
/**
*
* @param inOrder - inorder array
* @param start - start element in the inorder array for this method execution
* @param end - end element in the inorder array for this method execution
* @param preOrder - preorder array
* @return
*/
private Node<Integer> buildTree(int[] inOrder, int start, int end, int[] preOrder) {
Node<Integer> node = null;
if (start <= end && preOrderPointer < preOrder.length) {
int element = preOrder[preOrderPointer];
int position = inOrderElementPositionMap.get(element);
if (position >= start && position <= end) {
//build the Node for this element if we find a match
node = new Node<Integer>(element);
//increment the iterating pointer only where there is a match
preOrderPointer++;
//now divide the array into two subtrees, and build nodes for each of them recursively
node.left = buildTree(inOrder, 0, position-1, preOrder);
node.right = buildTree(inOrder, position+1, end, preOrder);
}
}
return node;
}
public static void main(String[] args) {
Node<Integer> root = new Node<Integer>(10);
Node<Integer> node4 = new Node<Integer>(4);
root.left = node4;
Node<Integer> node5 = new Node<Integer>(5);
root.right = node5;
Node<Integer> node6 = new Node<Integer>(6);
Node<Integer> node9 = new Node<Integer>(9);
node4.left = node6;
node4.right = node9;
Node<Integer> node11 = new Node<Integer>(11);
Node<Integer> node3 = new Node<Integer>(3);
node5.left = node11;
node5.right = node3;
Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node7 = new Node<Integer>(7);
node6.left = node1;
node9.right = node7;
BinaryTree<Integer> tree = new BinaryTree<Integer>(root);
System.out.print("InOrder : ");
tree.printInOrder();
System.out.println();
System.out.print("PreOrder : ");
tree.printPreOrder();
TreeExercise exercises = new TreeExercise();
System.out.println("\ncreating new tree...");
BinaryTree<Integer> newTree = exercises.buildTree("1 6 4 9 7 10 11 5 3", "10 4 6 1 9 7 5 11 3");
System.out.println("New Tree");
System.out.print("InOrder : ");
newTree.printInOrder();
System.out.println();
System.out.print("PreOrder : ");
newTree.printPreOrder();
}
}
public static class TreeNode{
TreeNode left, right;
int val;
}
public static TreeNode rebuild(int[] inOrder, int[] preOrder){
return rebuildRecur(inOrder, 0, inOrder.length, preOrder, 0);
}
private static TreeNode rebuildRecur(int[] inOrder, int inStart, int inEnd, int[] preOrder, int preIndex){
if(inOrder > inStart){
return null;
}
TreeNode node = new TreeNode();
node.val = preOrder[preIndex];
int splitIndex = -1;
for(int i = inStart; i < inEnd; i++){
if(inOrder[i] == node.val){
splitIndex = i;
break;
}
}
node.left = rebuildRecur(inOrder, inStart, splitIndex, preOrder, preIndex+1);
node.right = rebuildRecur(inOrder, splitIndex + 1, inEnd, preOrder, preIndex + (splitIndex - inStart + 2 ));
}
Assuming valid input:
class BstNode
{
public:
BstNode(int _data) : data(_data), left(nullptr), right(nullptr) {};
int data;
BstNode* left;
BstNode* right;
};
BstNode* rebuild_bst(int* pre, int* in, int n)
{
if (0 == n) return nullptr;
auto data = pre[0];
auto root = new BstNode(data);
auto i = 0;
for (; i < n; ++i)
{
if (data == in[i]) break;
}
root->left = rebuild_bst(pre + 1, in, i);
root->right = rebuild_bst(pre + i + 1, in + i + 1, n - i - 1);
return root;
}
import java.io.*;
import java.util.*;
class Tree{
int key;
Tree right;
Tree left;
Tree(int key){
this.key=key;
this.right=null;
this.left=null;
}
}
public class TreeForm{
static int[] inorder;
static int[] preorder;
public static void main(String[] args){
try{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] inorderStr=br.readLine().split(" ");
inorder=new int[inorderStr.length];
String[] preorderStr=br.readLine().split(" ");
preorder=new int[preorderStr.length];
for(int i=0;i<inorder.length;i++)inorder[i]=Integer.parseInt(inorderStr[i]);
for(int i=0;i<inorder.length;i++)preorder[i]=Integer.parseInt(preorderStr[i]);
Tree tr=makeTree(inorder,0,inorder.length-1);
// if(tr!=null)
postorderTree(tr);
//else{
//System.out.println("sry No Tree");
//}
}catch(IOException e){
System.out.println(e);
}
}
static int p=-1;
public static Tree makeTree(int[] a, int i,int j)
{++p;
if(i<a.length && p<a.length){
if(i==j){
return new Tree(a[i]);
}
else{
int index=find(preorder[p]);
Tree root=new Tree(a[index]);
root.left=makeTree(a, i, index-1);
root.right=makeTree(a,index+1,j);
// p++;
return root;
}
}else{
return null;
}
}
public static int find(int key){
int k=-1;
for(int i=0;i<inorder.length;i++){
if(inorder[i]==key){
k=i;
break;
}
}
return k;
}
public static void postorderTree(Tree t){
if(t!=null){
postorderTree(t.left);
postorderTree(t.right);
System.out.println(t.key);
//inorderTree(t.right);
}
}
}
CPU O(nlogn) Memory O(1):
Just keep inserting the pre-order elements to a tree.
For those asking about duplicates if the tree was created with a consistent algorithm then this solutions would work.
Otherwise you need to do a more complex O(n) algorithm which works for certain case but definitely I would avoid in an interview.
public static Node PreOrderBuildTree(int[] preOrder)
{
Node result = null;
foreach(int data in preOrder)
{
result = BST_PreOrderInsert(result, data);
}
}
private static Node BST_PreOrderInsert(Node head, int data)
{
if(head == null)
return new Node(data);
Node current = head;
Node prev = null;
while(current != null)
{
prev = current ;
if(current .Data >= data)
{
current = current .Right;
}
else
{
current = current .Left;
}
}
if(prev.Data >= data)
{
prev.Rigth = new Node(data);
}
else
{
prev.Right = new Node(data);
}
return head;
}
CPU O(n) Memory (n) Algorithm:
Call recursively maintaining the min and max based the side that you go.
It inserts nodes if they are within bounds.
Otherwise:
When out of bound less than the min means we are done with the Left side.
When out of bound been more than max means that we are done with the Right side.
This approach has a CPU order of growth of O(n) as the insertion is done at the lowest possible level thus not needing to traverse the entire tree to insert a new element.
The drawback is that in the worst case the Memory order of growth is O(n) due to call stack.
public static public static Node PreOrderBuildTree(int[] preOrder)
{
if(preOrder == null || preOrder.Length == 0) return null;
Node result = preOrder[0];
CoreBuildTree(
result,
preOrder,
1,
int.MinValue,
int.MaxValue);
return result;
}
private int CorePreOrderBuildTree(
Node head,
int[] preOrder,
int pos,
int min,
int max)
{
// If we are at the end we are done
if(preOrder.Length == pos)
return pos;
int data = preOrder[pos];
// This is for the Right Side
if(data >= head.Data && data <= max)
{
head.Rigth = new Node(data);
pos++;
pos = CoreBuildTree(
head.Right,
preOrder,
pos,
head.Data,
max);
}
// This is for the left side there still element left
if(pos != preOrder.Legnth)
{
data = preOrder[pos];
if(data <= head.Data && data <= min)
{
head.Left = new Node(data);
pos++
pos = CoreBuildTree(
head.Left,
preOrder,
pos,
min,
head.Data);
}
}
return pos;
}
The answer is yes and the solution is:
- tested.candidate March 22, 20151. Take the first element of the pre-order list
2. Find that element in in-order list and split that list into two lists - in-order before and in-order after
3. Similarly, for the pre-order list remove the first element and split it into two parts of the same length as in point 2 - pre-order before and pre-order after
4. Apply this function recursively to "before" and "after" lists