VMWare Inc Interview Question
Software Engineer / DevelopersCountry: United States
Maybe the last statement should be :
return isPostTraversalOfBST(arr, i) &&
isPostTraversalOfBST(arr + i, n - 1);
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.
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.
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);
}
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.
*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.
***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)
#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;
}
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;
}
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.
- uuuouou April 22, 2014