## VMWare Inc Interview Question for Software Engineer / Developers

Country: United States

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

We know in BST root is bigger than all nodes in left subtree and is no larger than all nodes in right subtree. Thus, if the array is a post traversal of a BST, then arr[n-1] can divide the array into two parts arr[0, i) and arr[i, n-1), where
(1)each item in arr[0, i) is less than arr[n-1]
(2)each item in arr[i, n-1) is not less than arr[n-1]
(3)both arr[0, i) and arr[i, n-1) are post traversals of BSTs.

``````bool isPostTraversalOfBST(int arr[], int n)
{
if(n < 2) return true;

int i = 0;
//try to find out the beginning of right subtree's traversal
for(; arr[i] < arr[n-1]; ++i) ;
//check if all arr[i,n-1) >= arr[n-1]
for(int j = i + 1; j + 1 < n; ++j){
if(arr[j] < arr[n-1]) return false;
}
//check if both two parts are post traversals of BSTs
return isPostTraversalOfBST(arr, i) &&
isPostTraversalOfBST(arr + i, n - i - 1);
}``````

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

Maybe the last statement should be :
return isPostTraversalOfBST(arr, i) &&
isPostTraversalOfBST(arr + i, n - 1);

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

This is a nice solution. Would this work if the tree is as follows?

1
\
2

This should lead to a post traversal of [2, 1].

Hand simulating the code, I get the result of false. Yet, this tree does follow the BST property that every node in the left subtree of a node is less than the node and every node in the right subtree of a node is greater than the node.

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

For a binary tree inorder traversal and either a postorder or preorder traversal can uniquely identify the tree.
The inorder sequence will resolve the left-right problem, and the other sequence (pre or post) will tell us the roots of the various subtrees. For example, if inorder is CBA, and preorder is CAB, then we know that C is at the root, and both B and A are in the right subtree.
In short to reconstruct the BT from the array we need at least two types of traversals. I don't think it is feasible to reconstruct BT with only post order traversal.

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

exactly

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

You're right. We can not reconstruct from only the postorder traversal. We can reconstruct the tree only if we already know that it is a BST. In the general case it needs postorder+ inorder or preorder+inorder. !!!! in the general case postorder+preorder is not enough either

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

Nice question! :-)

I have a solution with O(n) running time for this. We are going to traverse the array from the end. The idea is to maintain a collection of legal sub-trees to enter and to find a fit for the current element in those sub-trees. Note that, in the postorder traversal, we are always sure that all nodes in the left sub-tree of a given node appear before all nodes in the right sub-tree of that node. Knowing this, we can conclude that all sub-trees in our collection that are to the right of the current fit (for the current element), all become illegal and should be discarded. This observation tells us what data structure we should be using, and that DS is stack. The structure for the sub-trees is an implementation detail and you could get a sense of it in the following code.

My C++ implementation:

``````#include <iostream>
#include <stack>

using namespace std;

const int INF = (-1) ^ (1 << 31);

class TreeNode{
private:
int data;
TreeNode *left, *right, *par;
public:
TreeNode()
:left(NULL), right(NULL), par(NULL) { }
TreeNode(TreeNode *prnt, int val)
:data(val), left(NULL), right(NULL), par(prnt)
{
if (prnt == NULL)
return;

if (data < prnt->data)
prnt->left = this;

else
prnt->right = this;
}
int getVal()		{ return this->data; }
TreeNode* getRight(){ return this->right; }
TreeNode* getLeft()	{ return this->left; }
TreeNode* getPar()	{ return this->par; }
};

struct StackElem{
int LB, RB;
TreeNode *par;
StackElem(int l, int r, TreeNode *p)
:LB(l), RB(r), par(p){ }
};

bool fits(int b, int a, int c)
{
return (b >= a && b <= c);
}

pair <bool, TreeNode*> solve(int *ary, int n)
{
if (!n)
return make_pair(true,(TreeNode *) NULL);

TreeNode* root = new TreeNode(NULL, ary[n - 1]);

stack <StackElem *> stk;

stk.push(new StackElem(-INF, ary[n - 1], root));
stk.push(new StackElem(ary[n - 1], INF, root));

for (int i = n - 2; i >= 0; i--)
{
while (true)
{
StackElem *cur = stk.top();
stk.pop();

if (cur->RB < ary[i])
return make_pair(false,(TreeNode *) NULL);

if (fits(ary[i], cur->LB, cur->RB))
{
TreeNode *newNode = new TreeNode(cur->par, ary[i]);
stk.push(new StackElem(cur->LB, ary[i], newNode));
stk.push(new StackElem(ary[i], cur->RB, newNode));
break;
}
}
}

return make_pair(true, root);
}``````

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

``In the question they mentioned it is binary tree, and has given only one order i.e, but it is not possible to construct tree from a single order, at least we need any two tree traversals.``

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

Not any 2. The inorder should be one of them.

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

*only post order has given,

If we assume that the given binary tree is complete binary tree, then we can construct the tree as uuuouou@ mentioned in his or her first comment.

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

***EDIT: The OP HAS actually mentioned it should be a BST. Read the statement carefully. ***

Come on guys! It is trivial to construct a binary tree with only one traversal given to us. We can simply return a chain. No big deal! The OP certainly has forgotten to mention it is a BST. If you take a look at the examples, you'd know it anyway. Try to solve it for a BST. It actually is fun to try to find a way to do it in O(n)

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

``````#include<iostream>
#include<cstdlib>
#include<stack>
#include<climits>

using namespace std;

struct Tree
{
int value;
Tree *left;
Tree *right;

Tree(int i)
{
value=i;
left=NULL;
right=NULL;
}
};

void constructTree(Tree **node,int value)
{
if((*node)==NULL)
{
*node = new Tree(value);
}
else if((*node)->value<value)
constructTree(&((*node)->right),value);

else
constructTree(&((*node)->left),value);
}

void match(bool &flag, int val)
{
static int num= INT_MIN;
if(val>num)
{
num=val;
}
else
flag=false;
}

bool binaryTree(Tree *node)
{
bool flag=true;
stack<Tree*> st;

while((st.empty() || node)&&flag)
{
if(node!=NULL)
{
st.push(node);
node=node->left;
}
else
{
node=st.top();
st.pop();
match(flag,node->value);
node=node->right;
}
}

return flag;
}

int main()
{
int size;
cin>>size;
int a[size];
for(int i=0;i<size;i++)
{
cin>>a[i];
}

Tree *root=new Tree(a[size-1]);

for(int i=size-2;i>=0;i--)
{
constructTree(&root,*(a+i));
}

bool b = binaryTree(root);

cout<<"out : "<<b;

return EXIT_SUCCESS;
}``````

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

sorry i did a mistake

``````bool binaryTree(Tree *node)
{
bool flag=true;
stack<Tree*> st;

while((st.empty() || node)&&flag)
{
if(node!=NULL)
{
st.push(node);
node=node->left;
}
else
{
node=st.top();
st.pop();
match(flag,node->value);
node=node->right;
}
}

return flag;
}``````

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

``````bool binaryTree(Tree *node)
{
bool flag=true;
stack<Tree*> st;

while((!st.empty() || node)&&flag)
{
if(node!=NULL)
{
st.push(node);
node=node->left;
}
else
{
node=st.top();
st.pop();
match(flag,node->value);
node=node->right;
}
}

return flag;
}``````

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.