Qualcomm Interview Question
Country: India
void inOrder (Tree *current) {
while (current) {
if (current->left) {
push (current);
current = current->left;
} else {
print (current);
while (current && current->right == NULL)
current = pop ();
current = current->right;
}
}
This is actually an interesting question.
Using the Inorder, given a and b, we can determine whether a > b or a < b, say by using a hastable and recording the index. We won't code that up and assume we are given the compare function.
(I am assuming all distinct).
Now given the preorder, we try to construct the tree, and insert the new value into the appropriate location.
We maintain a stack. If the new value to be entered is smaller than the value at the top of the stack, the it becomes the left child.
If it is greater, we keep popping until we find a suitable parent.
Here is some quick C++.
// Inorder is implicit.
Tree *FromPreorderInorder(std::vector<int> preorder) {
std::stack<Tree *> nodes;
Tree *root = new Tree(preorder[0]);
nodes.push(root);
for (int i = 1; i < preorder.size(); i++) {
int val = preorder[i];
Tree *top = nodes.top();
// Left child.
if (val < top->Value) {
top->Left = new Tree(val);
nodes.push(top->Left);
continue;
}
// Right child of some node.
// Find it.
Tree *parent = NULL;
while (val > top->Value) {
parent = top;
nodes.pop();
if (nodes.empty()) break;
top = nodes.top();
}
parent->Right = new Tree(val);
nodes.push(parent->Right);
}
return root;
}
typedef struct Node_tag {
int value;
struct Node_tag* left;
struct Node_tag* right;
} Node;
int SearchNodeinOrder(int value, int* inorder, int left, int right)
{
while (left <= right)
{
int middle = (left + right) / 2;
if (inorder[middle] == value) return middle;
else if (inorder[middle] < value) left = middle+1;
else right = middle-1;
}
return -1;
}
Node* BuildBST(int* inorder, int* preorder, int size)
{
int cur;
int alloc_cur = 0;
typedef struct {
int left_in;
int right_in;
int left_pre;
int right_pre;
Node* parent;
int isLeft;
} TREE_STACK_ENTRY;
Node* r = NULL;
Node* tmp = (Node*)malloc(sizeof(Node)*size);
TREE_STACK_ENTRY* s = (TREE_STACK_ENTRY*) malloc(sizeof(TREE_STACK_ENTRY* size));
if (!s || !tmp)
{
if (s) free(s);
if (tmp) free(tmp);
return NULL;
}
memset(s, 0, sizeof(TREE_STACK_ENTRY)*size);
s[0].left_in = s[0].left_pre = 0;
s[0].right_in = s[0].right_pre = size-1;
s[0].parent = NULL;
s[0].isLeft = 1;
cur = 1;
while (cur)
{
Node* n;
int pos;
TREE_STACK_ENTRY e = s[cur-1];
cur--;
n = &tmp[alloc_cur++];
n->value = preorder[e.left_pre];
if (e.left_in != e.right_in)
{
pos = SearchNodeinOrder(n->value, inorder, e.left_in, e.right_in);
if (e.left_in < pos)
{
s[cur].left_in = e.left_in;
s[cur].right_in = pos-1;
s[cur].left_pre = e.left_pre + 1;
s[cur].right_pre = e.left_pre + pos - e.left_in;
s[cur].parent = n;
s[cur].isLeft = 1;
cur++;
}
if (pos < e.right_in)
{
s[cur].left_in = pos+1;
s[cur].right_in = e.right_in;
s[cur].left_pre = e.left_pre + 1 + pos - e.left_in;
s[cur].right_pre = e.right_pre;
s[cur].parent = n;
s[cur].isLeft = 0;
cur++;
}
}
if (n->parent)
{
if (n->isLeft) n->parent->left = n;
else n->parent->right = n;
}
else r = n;
}
free(s);
return r;
}
a!o! forget to handle the -1 search result.
typedef struct Node_tag {
int value;
struct Node_tag* left;
struct Node_tag* right;
} Node;
int SearchNodeinOrder(int value, int* inorder, int left, int right)
{
while (left <= right)
{
int middle = (left + right) / 2;
if (inorder[middle] == value) return middle;
else if (inorder[middle] < value) left = middle+1;
else right = middle-1;
}
return -1;
}
Node* BuildBST(int* inorder, int* preorder, int size)
{
int cur;
int alloc_cur = 0;
typedef struct {
int left_in;
int right_in;
int left_pre;
int right_pre;
Node* parent;
int isLeft;
} TREE_STACK_ENTRY;
Node* r = NULL;
Node* tmp = (Node*)malloc(sizeof(Node)*size);
TREE_STACK_ENTRY* s = (TREE_STACK_ENTRY*) malloc(sizeof(TREE_STACK_ENTRY* size));
if (!s || !tmp)
{
if (s) free(s);
if (tmp) free(tmp);
return NULL;
}
memset(s, 0, sizeof(TREE_STACK_ENTRY)*size);
s[0].left_in = s[0].left_pre = 0;
s[0].right_in = s[0].right_pre = size-1;
s[0].parent = NULL;
s[0].isLeft = 1;
cur = 1;
while (cur)
{
Node* n;
int pos;
TREE_STACK_ENTRY e = s[cur-1];
cur--;
n = &tmp[alloc_cur++];
n->value = preorder[e.left_pre];
if (e.left_in != e.right_in)
{
pos = SearchNodeinOrder(n->value, inorder, e.left_in, e.right_in);
if (pos == -1)
{
free(s);
free(tmp;
return NULL;
}
if (e.left_in < pos)
{
s[cur].left_in = e.left_in;
s[cur].right_in = pos-1;
s[cur].left_pre = e.left_pre + 1;
s[cur].right_pre = e.left_pre + pos - e.left_in;
s[cur].parent = n;
s[cur].isLeft = 1;
cur++;
}
if (pos < e.right_in)
{
s[cur].left_in = pos+1;
s[cur].right_in = e.right_in;
s[cur].left_pre = e.left_pre + 1 + pos - e.left_in;
s[cur].right_pre = e.right_pre;
s[cur].parent = n;
s[cur].isLeft = 0;
cur++;
}
}
if (n->parent)
{
if (n->isLeft) n->parent->left = n;
else n->parent->right = n;
}
else r = n;
}
free(s);
return r;
}
Do it recursively. Assume the lists are arrays.
Pseudocode:
fn tree(inorder, postorder){
if array length is 1, return new node with the only value (termination condition)
find position of postorder[0] in inorder
split inorder there into inorder_left, inorder_right (leaving out the number at postorder[0])
find position of the last value in inorder_left in postorder
split postorder at the position after that (again, leave out the first number)
new node with value postorder[0]
node.left = tree(inorder_left, postorder_left)
node.right = tree(inorder_right, postorder_right)
return node
}
using a queue, construct the tree level by level. Each queue node stores the start, end index in the in order and preorder lists.
- Jason November 03, 2013