Amazon Interview Question
Software Engineer / Developerswhy do you need BFS?
this can be done using a inorder traversal
first declare a n*n matrix..
then define a function as follows.
void convert2matrix(node *root, node *parent){
if(root != NULL){
if(par != NULL)
matrix[par->data][root->data] = 1;
convert2matrix(root->left, root);
convert2matrix(root->right, root);
}
}
invoke this function using : convert2matrix(root, NULL);
i think this will work fine..
just a bit of correction above..
replace par with parent
and
replace statement matrix[par->data][root->data] = 1 with matrix[root->data][parent->data] = 1
This method seems to be wrong as it will just put 1 on the immediate parent and not on the super parent. For example for the node D it will say its parent is only B and put 1 only in that slot in the matrix(DB) and not put it in (DA)
Correct me if I am wrong??
My solution was... do any traversal and save all node in a hash table such that <k,v> = <node, its parent>
Then populate the matrix using the table.
Space complexity = O(n)
Running time complexity = O(nlogn)
We can implement it by using the array representation of binary tree.In array representation the 0th element is the root, the index at 1 is left child of the root and at index 2 is right child of the root... and so on.
So if a node's index no is index then its left child will be 2*index + 1 , right child will be 2*index + 2, node's parent will be (index - 1)/2 --> integer division with no remainder. Hence the code goes like following
initialize the array as arr[numOfNodes][numOfNodes]
Int parent Index = 0;
For(int i= numOfNodes - 1 ; i >= 0; i--){
Do{
Parent Index = (I - 1)/2;
Arr[i][parentIndex] = 1;
}while( parentIndex > 0)
}
correct me if I am wrong.
correct solution can be this:
void convert2matrix(node *root, node *parent){
if(root != NULL)
{
if(parent != NULL)
{
memcpy(matrix[root->data], matrix[parent->data], n*sizeof(int));
matrix[root->data][parent->data] = 1;
}
convert2matrix(root->left, root);
convert2matrix(root->right, root);
}
}
basically, copy the parent data . and just set matrix[root][parent] = 1;
STACK* stack2 = createStack();
Int createMatrix(STACK* stack, NODE* node)
{
NODE* tmp;
If(node->left != NULL || node->right != NULL)
{
Stack->push(node);
If(node->left != NULL) createMatrix(stack, node->left);
If(node->right != NULL) createMatrix(stack, node->right);
}
While(!stack->empty())
{
Tmp = stack->pop();
SetMatrix(tmp->data, node->data);
Stack2->push(tmp);
}
While(!(stack2->empty())
{
Tmp = stack->pop();
Stack2->push(tmp);
}
Stack->pop();
Return;
}
void createMatrix(treenode *root, int matrix[][], int n) //n is size of tree
{
int i;
if (!root) return;
if (root->left) {
matrix[root->left][root->data] = 1;
for (i=0; i<n; i++) {
if (matrix[root->data][i])
matrix[root->left][i] = 1;
}
createMatrix(root->left, matrix, n);
}
if (root->right) {
matrix[root->right][root->data] = 1;
for (i=0; i<n; i++) {
if (matrix[root->data][i])
matrix[root->right][i] = 1;
}
createMatrix(root->right, matrix, n);
}
}
fill_matrix(int i,Node *root){
if(root){
Parent = [i/2];
if(Parent>0){
while(Parent > 0){
A[i][Parent]=1;
Parent=[Parent/2];
}
}
fill_matrix(2*i,root->left);
fill_matrix(2*i+1,root->right);
}
}
}
}
}
Prashant's answer is best here I guess. But, let me give my two cents.
Call matrix by matrix(root, new ArrayList<BinaryTree());
I am just print the nodes, you can use a matrix in case you life.
private static void matrix(BinaryTree root, ArrayList<BinaryTree> list){
if(root == null){
return;
}
list.add(root);
matrix(root.left, list);
matrix(root.right, list);
list.remove(list.size()-1);
System.out.println();
for(int i = 0 ; i < list.size();i++){
BinaryTree parent = list.get(i);
System.out.print("[" + parent.data + "->" + root.data + "]");
}
}
void VerticalSum(TreeNode* node,int column, int *sum)
{
if(node == null)
{
return ;
}
sum[column]+= node->Data;
VerticalSum(node->Left,column-1,sum);
VerticalSum(node->Right,column+1,sum);
return ;
}
void VerticalSum()
{
int sum[1000]={0};
VerticalSum(_root,499,sum);
int i = 499;
while(sum[i] != 0) i--;
i++;
for(int j=1;sum[i]!=0;i++,j++)
{
printf("Vertical-%d = %d\n",j,sum[i]);
}
}
//assume matrix is big enough matrix initialized with 0.
void f(NODE* root, int** matrix)
{
Stack stack;
int[] ChildCounts[];
(NODE*)[] Nodes;
int p1=0, p2=0;
stack.push(root);
while(!stack.empty())
{
NODE *node = stack.pop();
ChildCounts[p2]=count(node's children);
Nodes[p2++]=node;
stack.push(node->Children); //handle left and right respectively
if node != root
NODE* parent = Nodes[p1];
if(--ChildCounts[p1] == 0)
p1++;
//function GetIndex gets index of this node from Nodes array.
matrix[GetIndex(node)][GetIndex(parent)]=1;
for(n = GetIndex(parent)-1 to 0)
if matrix[parent][n]==1
matrix[node][n]=1
}
}
Create a nXn matrix where n is the size of the Binary tree.
- Ravi May 26, 2010Do a BFS, whenever you are adding nodes to the queue, set the indexes where represent the current node and its parents. Note that the parents are already set for the current node.