Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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.
I cunt understand this logic. Suppose the inorder array of a BST is: 62,60,80,65,90
then how to construct a BST??
@neel: LOL... inorder array of a BST always in ascending order.. else it wont be a BST..
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
@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).
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
@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.
{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....
}
{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....
}
This is not O(n)
For each element it requires log(n) comparisons
(with stack top) and popping
Its a nlog(n) solution
^^ 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)
@mos you are right
Here is a more simple solution with O(nlogn) complexity.
pseudo code
P[n] = preorder BST array
node *head = null;
void
createBst()
{
for (i = n; i > 0; i++) /* O(nlog n) */
{
node *newNode = createnode(P[i]);
if (head == null)
head = newNode;
else
{
bstinsert(head, newNode); /* O(log n) */
}
}
}
@ 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..
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;
}
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
@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.
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
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
@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'.
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;
}
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.
//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!
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).
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;
}
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.
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]);
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
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.
@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...
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.
My bad...I didn't read through. It's pre order, which is not equivalent to a linked list. Please ignore that part.
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......!!
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! :)
#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;
}
void printinorder(struct node* head)
{
if(head==NULL)
return;
printinorder(head->left);
printf("%d",head->data);
printinorder(head->right);
}
int main()
{
struct node* tree;
int pre[]={6,2,1,4,3,5,8,7,9};
tree=consbst(pre,0,8);
printinorder(tree);
getch();
}
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;
}
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;
}
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.
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.
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...
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;
}
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;
}
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) {
leftSubTree.add(nodeVal);
} else if (rootNodeVal < nodeVal) {
rightSubTree.add(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);
}
}
// 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;
}
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?
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
- Anshu Kumar July 27, 20121. 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.
Please check ideone.com/VohnS for details