Amazon Interview Question Developer Program Engineers
for the 1st approch, how you could write tree nodes into array like what you say, in other word, when you stop your scan on the tree. In your example, you used level-order. The issuse is how could you know -1 on the 15th position is the last one of the tree....
For the 2nd approach, preorder/inorder/postorder would have the same problem. You cannot tell whether a particular number is left or right or cousin's child. If you mark as NULL, how to stop your scan,i.e, how could you make sure there is no other valid nodes in a deeper level.
You can store completely and reconstruct identically a bst, by storing it's pre order traversal.
To reconstruct the bst identical to original, read the file and after reading each key, insert into the bst using a simple binary search tree insert.
Store preorder and inorder in file and reconstruct back:
int pre[10] = {50,40,25,70,5,45,20,10,35,85};
int in[10] = {70,25,40,5,45,50,10,20,35,85};
int search_result(int d, int root_d)
{
int i=0;
for(; i<10; i++)
{
if(in[i] == d || in[i] == root_d)
break;
}
if(in[i] == d)
return 1;
else
return 0;
}
void func(node **root, int d)
{
if(*root == NULL)
{
*root = (node*)malloc(sizeof(node));
(*root)->data = d;
(*root)->left = (*root)->right = NULL;
}
else if(search_result(d, (*root)->data) == 1)
func(&(*root)->left, d);
else
func(&(*root)->right, d);
}
void construct_tree_from_pre_in_order(node**root)
{
for(int i=0; i<10; i++)
func(&(*root), pre[i]);
}
I think you can store the nodes in an array just the way its done for heap
node : Index : i
node.left : Index : 2i
node.right: Index : 2i + 1
The tree can be reconstructed from it easily, although it would require more space
use a array list & keep a identifier for null value
- Anonymous February 10, 2011start with root now
lets say root (12) have two children left (8) right (30) left of (8) is (4) right (10) left of (4) is NULL right is (6)
Keep this in array
12 08 30 04 10 -1 -1 -1 06 -1 -1 -1 -1 -1 -1
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
now start with root 12
children is 08-left 30-right
children of 08 is 04-left 10-right
children of 30 is NULL-left NULL-right
children of 04 is NULL-left 06-right
remaining is NULL
It will reconstruct same tree