CareerCup

Create a nXn matrix where n is the size of the Binary tree.
Do 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.

why 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..

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)

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);
}
}



}



}



}

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);
}
}



}



}



}

I think Ravi's answer seems good. While doing a BFS, the nodes that are enqueued can be set in the matrix.

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]);
	}

}

list={} //infact a vector
fun(root)
{
if(!root) return;
else{
for all elements X in list
mat[root->data][X->data]=1;
list.push(root);
fun(root->left);
fun(root->right);
list.remove(root);
}

}

//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  
  } 
}