## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
21
of 25 vote

This can be solved in O(n) only. The approach am using is, keep a separate stack of node pointers. Push on the 1st node. Keep on traversing the preorder traversal
1. if the value of stack top is more than the current node value, then make the current node left pointer of stack top.
2. if the value of stack top is less that current node value, keep popping from the stack till value of stack top is more than current node. Then make current node the right child of last popped element.
Push the current node on stack in both the cases.

It may seem like an O(n^2) algo, but we are pushing and popping every element on stack only once so this is O(n) time and space.

Comment hidden because of low score. Click to expand.
0

I think this is a nice sln with O(n) complexity

Comment hidden because of low score. Click to expand.
0

Great solution!
Used the idea(backward) of traversing pre-order of a tree using stack instead of recursion. This is another one of the good examples where it is usable over the recursion.

Comment hidden because of low score. Click to expand.
0

A nice non-recursive implementation.

Comment hidden because of low score. Click to expand.
0

I cunt understand this logic. Suppose the inorder array of a BST is: 62,60,80,65,90
then how to construct a BST??

Comment hidden because of low score. Click to expand.
0

@neel: LOL... inorder array of a BST always in ascending order.. else it wont be a BST..

Comment hidden because of low score. Click to expand.
0

This looks the same to me as making the first element A[0] as root, then inserting the next elements into the BST like you do into ordinary BST. Correct me if I am wrong

Comment hidden because of low score. Click to expand.
0

Very nice solution!

Comment hidden because of low score. Click to expand.
0

@babbupandey .. I too thought about the same thing..but each insert takes log(n) for BST and n inserts take n(log(n)). But the above soln says it is O(n).

Comment hidden because of low score. Click to expand.
0

Instead of going through log(n) steps to figure out where to insert the node, the above solution is maintaining the node pointers of all the nodes in the stack..reduces time ,increases space

Comment hidden because of low score. Click to expand.
0

@rkt - each insert takes O(h) time, where 'h' is the height of the tree; therefore when we are inserting any node, we are making at most 'h' comparisons... which is what his algorithm seems to be doing.

Comment hidden because of low score. Click to expand.
0

{1 caseis missing in the given solution!!! that case is when we are popping out the elements, what we need to do stack become empty????

In that case just make current node as right child of last popped node....
}

Comment hidden because of low score. Click to expand.
0

{1 case is missing in the given solution!!! that case is when we are popping out the elements, what we need to do stack become empty????

In that case just make current node as right child of last popped node....
}

Comment hidden because of low score. Click to expand.
0

This is not O(n)

For each element it requires log(n) comparisons
(with stack top) and popping

Its a nlog(n) solution

Comment hidden because of low score. Click to expand.
0

^^ Elaborating

Case 1 is above solution will take only 1 comparison
Case 2 will take log(n) comparison with we want to insert right child

Case 2 will occur half the number of times unless there are only decreasing elements in the given list

Therefore:

Total complexity = n/2 + n/2 log (n/2) which implies (nlogn)

Comment hidden because of low score. Click to expand.
0

In ideone.com/VohnS

``tmp->value > s.top()->value``

should be

``tmp->value >= s.top()->value``

.

Comment hidden because of low score. Click to expand.
0

@mos you are right

Here is a more simple solution with O(nlogn) complexity.
pseudo code

``````P[n] = preorder BST array

void
createBst()
{
for (i = n; i > 0; i++) /* O(nlog n) */
{
node *newNode = createnode(P[i]);
else
{
bstinsert(head, newNode); /* O(log n) */
}
}
}``````

Comment hidden because of low score. Click to expand.
0

@ mos .. its an O(n) solution .. take paper and pen ... work one example .. an element is pushed and poped only once in its life time..

Comment hidden because of low score. Click to expand.
0

``````public TreeNode build(int[] val)
{
Stack<TreeNode> ns = new Stack<TreeNode>();
TreeNode root = new TreeNode(val[0]);
ns.push(root);
TreeNode last = null;
for(int i = 1; i < val.length; i++)
{
TreeNode n = new TreeNode(val[i]);
if(val[i] < ns.peek().val)
{
ns.peek().left = n;
}
else
{
for(last = ns.pop(); ns.size() > 0 && ns.peek().val <= val[i]; ns.pop());
if(ns.size() == 0)
{
last.right = n;
}
else
{
ns.peek().left = n;
}
ns.push(n);
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Looks like this algorithm breaks for this array.

If you follow this algorithm, at 14, it will make 14 the right child of 10, instead of 12 (which is 14's correct parent)

[20, 15, 10, 5, 4, 8, 6, 12, 14, 18, 16, 19, 25, 30, 28, 29]

``````20
/           \
15               25
/         \                \
10            18             30
/   \            /    \          /
5    12     16   19     28
/  \       \                          \
4    8     14                       29
/
6``````

Comment hidden because of low score. Click to expand.
0

@Nan :
It works fine. Do it on paper, u'll get.
When 12 comes, 10 will be poped and made 12 as right child of 10. when 14 comes, 12 will be poped and made right child of 12.

Comment hidden because of low score. Click to expand.
0

I think the correct solution would be :
Make and extra stack and the structure for the tree nodes
Iterate the array and push the first element in the stack and make it the root node.
1. while iterating , if you found smaller number than the previous array element ,than make the the left node of the current element and push in stack.

2. if the larger element is found , pop the top element and make it right child to the top element now and than remove the top element and push it in the stack, also if the stack is empty then first make it right child and then remove the top element and then push it

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This isn't quite correct. For example:

say you have an array like {10,5,1,6}

You start and make 10 the root, then following this algorithm, you set 5 and 1 to be the the sequential left-children, so far so good. Then you hit 6, following the algorithm, you pop back up to 10 and set it as 10's right sub-child. Not-correct

Comment hidden because of low score. Click to expand.
0

@CollinSchupman : read the answer correctly... "keep popping from the stack till value of stack top is more than current node. Then make current node the right child of last popped element" --> while inserting '6' , you pop till stack top is 10, and last poped element is 5, make '6' as right child of '5' and push '6'.

Comment hidden because of low score. Click to expand.
0

Try this algorithm on 100,50,60,70,80,90 and you will see where is the problem.

Comment hidden because of low score. Click to expand.
1
of 5 vote

``````ConstructBST(int pre[],int l,int h)
{
if(l>h) return NULL;
temp=getNode(pre[l]);
if(l==h) return temp;
for(i=l+1;i<=h;i++)
if(pre[i]>pre[l])
break;
temp->left=ConstructBST(pre,l+1,i-1);
temp->right=ConstructBST(pre,i,h);
return temp;
}``````

Comment hidden because of low score. Click to expand.
0

``````for(i=l+1;i<=h;i++)
if(pre[i]>pre[l])
break;``````

Hmm this lead to O(n) per level on an unbalanced tree. Which means that this algorithm will take O(n^2). Is there an O(n) solution? Nvm probably not.

Comment hidden because of low score. Click to expand.
0

order is:

T(n) = 2*T(n/2) + O(n) -> which is O(nlog(n)) and not O(n^2)

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````//l=size of array
node *buildbst(int pre[], int &start,int min,int max)
{
if( start>l)
return NULL;
if(preorder[start]>max && preorder[start]<min)
return NULL;
node *root;
root=malloc(sizeof(node));
root->data=pre[start++];
root->left=buildbst(pre,start,min,root->data);
root->right=buildbst(pre,start,root->data,max);
return root;
}
please correct me if i am wrong!``````

Comment hidden because of low score. Click to expand.
0

Looks right.

Comment hidden because of low score. Click to expand.
0

Except the && should be ||.
(if > max OR < min)

Comment hidden because of low score. Click to expand.
1
of 1 vote

Ok here is an O(n) recursive version, which is hopefully correct, unlike my previous attempt.

``````Tree Create(Stream <T> preOrder) {
return CreateInternal(preOrder, T.MinValue, T.MaxValue);
}

Tree CreateInternal(Stream <T> preOrder, T min, T max) {

if (!preOrder.hasNext()) return null;

T value = preOrder.peek();

if (value < min || value > max) return null;

Tree root = new Tree(preOrder.next());

root->left = CreateInternal(preOrder, min, value);
root->right = CreateInternal(preOrder, value, max);

return root;
}``````

Since each failed peek corresponds to a null node in the tree, this is O(n).

Comment hidden because of low score. Click to expand.
0

We can add error checking by checking for preOrder.hasNext() in Create.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public static class TreeNode{
public int val;
public TreeNode left,right;

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

}

public static TreeNode construct(int[] arr, int low, int high){
if(low <= high){
TreeNode n = new TreeNode(arr[low]);
int i = low+1;
while(i < arr.length && arr[i] < arr[low])
i++;
n.left = construct(arr,low+1, i-1);
n.right = construct(arr,i, high);
return n;
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0

is it O(n) ? or O(n^2)?

Comment hidden because of low score. Click to expand.
0
of 4 vote

At first it seemed like a difficult question. But, if we work out, the pre-order traversal of a BST is one of the possible input order for reconstructing a BST.

Comment hidden because of low score. Click to expand.
0

Correct!
Just build the tree!

Comment hidden because of low score. Click to expand.
0

Building the BST tree is O(n*log(n)).
Building the BST from a pre-order traversal is O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems ordinary question.. i dont know in conform whether i am right.. its just ordinary insertion of node in BST.

``````public Tree insert(Tree tree,int element)
{
if(tree==null )
{
tree = new Tree();
tree.element = element;
tree.left = tree.right = null;
}
else if(element < tree.element)
tree.left = insert(tree.left, element);
else if(element > tree.element)
tree.right = insert(tree.right,element);

return tree;
}

// In main function
for(int i = 0;i< preorder.length;i++)
tree = insert(tree,preorder[i]);``````

Comment hidden because of low score. Click to expand.
0

its not easy to write optimized code.... lets there are the data is 10 9 8 7 6 5 4 3 2 1...here you will be calling 10 times the insert function... so the total complexity is n^2..
for 10 - one data to pass through
for 9 - you have to pass 10 and then 9
for 1 - you have to pass through 10-9-8-...-3-2-1 again and again...

what efficient code will not call the function this many times... it will call only once and insert all elements in O(n) time

Comment hidden because of low score. Click to expand.
0
of 2 vote

You can only construct BST if in-order and one of pre-order or post-order traversal is given. You can not construct from just pre-order.

Comment hidden because of low score. Click to expand.
0

i have constructed.. prove it wrong..
atleast i can learn few things..

Comment hidden because of low score. Click to expand.
0

@Jayanta. This is a BST, how hard is finding in-order from the pre-order? in-order is just the sorted form of pre/post-order in a BST...

Comment hidden because of low score. Click to expand.
0

For binary tree This is true. But BST has some properties of it's own and its not just any binary tree. For BST we can build with either post or pre order alone. But not with inorder alone

Comment hidden because of low score. Click to expand.
0
of 0 vote

Well, it can be created but it well be as good as a linked list. With in order and one other order.
It seems the interviewer wants to know if you know such concepts and if you ask more questions to get clarity.
But that's just my opinion.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Actually this problem can be solved.Some of you guys said that when only preorder is given then it is not possible....but it is possible...whatever the nodes are given...then sort it first according to the ascending order....then this outcome is inorder traversal...and now you have inorder and preorder traversal ...and u can easily construct the binary search tree....
But one thing i am clearly saying that if the given order is not possible to sort...then you never got the inorder and only this time it is not possible to construct a BST...!! I think it is usefull for u guys..anyway if i am wrong then pls reply me...i will check it and i can getover from my wrong idea......!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Its like a trick question - One just has the preorder traversal, and we need to build a tree!
If you remember, we can build a tree pretty fine with Preorder and Inorder traversal.
See the Preorder traversal as integer data in array.
And Inorder traversal = Sorted Copy of Array above
Viola! :)

Comment hidden because of low score. Click to expand.
0

This, of course, will be valid only for the special case of BST.

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````#include<stdio.h>
struct node{
int data;
struct node* left;
struct node* right;
};

struct node* consbst(int pre[],int k,int l)
{
struct node* tmp=(struct node*)malloc(sizeof(struct node));
if(l==k)
{
tmp->data=pre[k];
tmp->left=NULL;
tmp->right=NULL;
return tmp;
}

int i=k+1;

while(pre[k]>pre[i]&&i<l)
i++;
i--;
tmp->data=pre[k];
tmp->left=consbst(pre,k+1,i);
tmp->right=consbst(pre,i+1,l);
return tmp;
}
{
return;
}
int main()
{
struct node* tree;
int pre[]={6,2,1,4,3,5,8,7,9};
tree=consbst(pre,0,8);
printinorder(tree);
getch();
}``````

Comment hidden because of low score. Click to expand.
0

on running this program it will print the inorder traversal of the constructed tree with the given preorder traversal.
input array={6,2,1,4,3,5,8,7,9};
output array={1,2,3,4,5,6,7,8,9};

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Fix(int ara[], int len) {
if(!len) return NULL;
Node * p = NULL;
for (int i = 0; i < len; i++ ){
p = Insert(p, ara[i]);
}
}

Node * Insert(Node *p, int v) {
if (!p) {
p = new Node(v);
}
if (p->v <= v)
p->left = Insert(p->left, v);
else p->right = Insert(p->right, v);
return p;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

or you can use double pointer to avoid returning the new node address

Comment hidden because of low score. Click to expand.
0
of 0 vote

BST reconstruct(int[] preorder, int s, int e)
{
if(s==e)
return null;
BST root = new BST(preorder[s]);
if(preorder[s]>preorder[s+1])
{
int r = s + 1;
for(; r<e; r++)
{
if(preorder[s]<preorder[r])
break;
}
root.leftchild = reconstruct(preorder, s, r);
root.leftchild = reconstruct(preorder, r, e);
}
else
{
root.rightchild = reconstruct(preorder, s+1, e);
}

return root;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

for INORDER

#include<stdio.h>
#include<malloc.h>

typedef struct node{
int data;
struct node *l;
struct node *r;
}node;

node *getnode(int d){
node *temp= (node *)malloc(sizeof(node));
temp->data= d;
temp->l= NULL;
temp->r= NULL;
return temp;
}

node *BST(int A[], int min, int max){
int mid= (min+ max)/ 2;
node *temp;

if(max== min)
return getnode(A[min]);
else {
temp= getnode(A[mid]);
if(mid!= min)
temp->l= BST(A, min, mid-1);

temp->r= BST(A, mid+1, max);
return temp;
}
}
void Inorder(node *root){
if(root){
Inorder(root->l);
printf("%d--", root->data);
Inorder(root->r);
}
}

int main(){
int A[12]= {1, 5, 7, 8 ,9 ,12,13, 19, 25, 26, 27, 31};
node *root= BST(A, 0, 11);

Inorder(root);
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

We have O(n) solution to construct BST from a sorted array, why all this fuss here i mean stack and all. correct me if i misunderstood the question.

Comment hidden because of low score. Click to expand.
0

Ohh really. Care to elaborate the O(n) solution ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

We cannot construct a binary tree just when pre order is given But in case of BST we can. The reason being, if its a BST you can sort the given order which will be equivalent to inorder for that tree. Then we can use both in preorder and inorder traversal lists to built a BST.

Comment hidden because of low score. Click to expand.
0

Yeah, right!! but What's the issue in this question BST is given....and we don't need inorder to get BST back from preorder, check out the top most answer fo that...

Comment hidden because of low score. Click to expand.
0

how will you check the depth of the tree just with the preorder traversal ??

Comment hidden because of low score. Click to expand.
0

First we can construct the BST using first algorithm then if you want you can run a function to get hieght of the tree.......once read that algorithm you will get everything......

Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems like a simple recursive algorithm will do (which when simulated using the stack will be same as the top voted solution, I suppose)

``````Tree CreateTreefromPreOrder <T> (Stream <T> preOrder) {

Tree root = null;

if (preOrder.hasNext()) {
root = new Tree(preOrder.next());
}

if (preOrder.hasNext()) {
T child = preOrder.peek();
if (root->data > child) {
root->left = CreateTreeFromPreOrder(preOrder);
}
}
root->right = CreateTreeFromPreOrder(preOrder);
return root;
}``````

Comment hidden because of low score. Click to expand.
0

Ok, perhaps this has been posted before. Sorry.

Comment hidden because of low score. Click to expand.
0

And this might be wrong, actually.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Node* RebuildBST(vector<int> output)
{
int n=output.size();
if(n==0)
return NULL;
stack<Node*> myStack;
int i=0;
Node* root;
while(i<n)
{
int curVal=output[i];
Node* preNode=NULL,*prePreNode=NULL;
while(!myStack.empty())
{
preNode=myStack.top();
if(preNode->val>curVal)
break;
prePreNode=myStack.top();
myStack.pop();
}
Node* curNode=new Node;
curNode->val=output[i];
curNode->L=NULL;
curNode->R=NULL;
if(!preNode)
{
root=curNode;
}
else if(!prePreNode)
{
preNode->L=curNode;
}
else
{
prePreNode->R=curNode;
}
myStack.push(curNode);
i++;
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

enum TraversalType {
PREORDER, INORDER, POSTORDER;
}

public class ConstructTreeBack {
static Node root = new Node();
static TraversalType traversalType;

static void formSubTrees(List<Integer> treeList) {
if (traversalType.equals(TraversalType.PREORDER)) {
formSubTreesPreOrder(treeList);
} /*else if (traversalType.equals(TraversalType.INORDER)) {
formSubTreesInOrder(treeList);
} else if (traversalType.equals(TraversalType.POSTORDER)) {
formSubTreesPostOrder(treeList);
}  */

}

/*static void formSubTreesInOrder(List<Integer> treeList) {

}
*/
static void formSubTreesPreOrder(List<Integer> treeList) {
List<Integer> leftSubTree = new ArrayList<Integer>();
List<Integer> rightSubTree = new ArrayList<Integer>();

Iterator<Integer> it = treeList.iterator();

int rootNodeVal = it.next();
root.setValue(rootNodeVal);
root.setRoot(true);

while (it.hasNext()) {
int nodeVal = it.next();
if (rootNodeVal > nodeVal) {
} else if (rootNodeVal < nodeVal) {
}
}

if (leftSubTree.size() <= 3) {
Node left = formNode(leftSubTree);
root.setLeftNode(left);
} else {
formSubTreesPreOrder(leftSubTree);
}

if (rightSubTree.size() <= 3) {
Node right = formNode(rightSubTree);
root.setLeftNode(right);
} else {
formSubTreesPreOrder(rightSubTree);
}
}

static Node formNode(List<Integer> treeList) {
Node node = new Node();

if (traversalType.equals(TraversalType.PREORDER)) {
if (null != treeList.get(0)) {
node.setValue(treeList.get(0));
}
if (null != treeList.get(1)) {
node.setLeftNode(new Node(treeList.get(1)));
}
if (null != treeList.get(2)) {
node.setRightNode(new Node(treeList.get(2)));
}
}
if (traversalType.equals(TraversalType.INORDER)) {
if (null != treeList.get(1)) {
node.setValue(treeList.get(1));
}
if (null != treeList.get(0)) {
node.setLeftNode(new Node(treeList.get(0)));
}
if (null != treeList.get(2)) {
node.setRightNode(new Node(treeList.get(2)));
}
}
if (traversalType.equals(TraversalType.POSTORDER)) {
if (null != treeList.get(2)) {
node.setValue(treeList.get(2));
}
if (null != treeList.get(0)) {
node.setLeftNode(new Node(treeList.get(0)));
}
if (null != treeList.get(1)) {
node.setRightNode(new Node(treeList.get(1)));
}
}
return node;
}

public static void main(String[] args) {
Integer treeArrPreOrder[] = { 4, 2, 1, 3, 6, 5, 7 };
List<Integer> treeList = Arrays.asList(treeArrPreOrder);
traversalType = TraversalType.PREORDER;
root.setValue(treeArrPreOrder[0]);
root.setRoot(true);

formSubTrees(treeList);
System.out.println(root);

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// order is O(n) : T(n) = 2T(n/2) + log(n)
TreeNode* build_bst(vector<int>& a, int lo, int hi)
{
if (lo > hi) return NULL;
// do binary search for first true F F F F F T T T T T
//  F corresponds to all elements < a[lo]  and T corresponses > a[lo]. and we to find first True
int m = find_ele_greater(a, lo+1, hi, a[lo]);
TreeNode* root = new TreeNode(a[lo]);
root->left = build_bst(a, lo+1, m-1);
root->right = build_bst(a, m, hi);
return root;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Correct me if I'm wrong, but aren't there many different reconstructions? For example if the array is [1, 2, 3, 4, 5], just two possible reconstructions include
{
5
/
4
/
3
/
2
/
1

AND

3
/ \
2 4
/ \
1 5
}

Plus many more?

Comment hidden because of low score. Click to expand.
0

Dude is [1,2,3,4,5] preorder of any of the tree u have posted???
Just read the question properly before posting anything

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.