CareerCup

int matrix[N][N] = {0};

int main()
{
//Build a tree of n elements 
int arr[N];  // This array is used to store paths from root to leaf
ancestorMatrix(root, arr, 0);
return 0;
}

void ancestorMatrix(struct node *root, int arr[], int level, int matrix[])
{
if (!root)
return;
for(int i = level - 1; i >= 0; i --)
	matrix[root->data][result[i]] = 1; // The array contains all the predecessors of the current node
result[level++] = node->data; //Add your current node to the path array and send this array to its descendants 
if (root->left)
	ancestorMatrix(root->left, arr, level, matrix);
if (root->right)
	ancestorMatrix(root->right, arr, level, matrix);
}

Not exactly sure what the binary tree has to do with the matrix? Can you explain in more detail?

Just a basic doubt, r the elements of tree have values from 1.....n only or can have any value?

#include<stdio.h>
#include<stdlib.h>

struct tNode
{
int d;
struct tNode* l;
struct tNode* r;
};
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->d = data;
tNode->l = NULL;
tNode->r = NULL;

return(tNode);
}
void fillMat(struct tNode *root,int mat[][5],int count)
{
if(root==NULL)
return;

if((root->l!=NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
mat[root->d-1][(root->r)->d-1]=1;
}
else if((root->l!=NULL) && (root->r==NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
}
else if((root->l==NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->r)->d-1]=1;
}
else
{
return;
}
fillMat(root->l,mat,count);
fillMat(root->r,mat,count);
}
/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
int mat[5][5];
int i,j;

struct tNode *root = newtNode(1);
root->l = newtNode(2);
root->r = newtNode(3);
root->l->l = newtNode(4);
root->l->r = newtNode(5);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
mat[i][j]=0;
}
}
fillMat(root,mat,0);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
printf("%d",mat[i][j]);
}
printf("\n");
}
return 0;
}

#include<stdio.h>
#include<stdlib.h>

struct tNode
{
int d;
struct tNode* l;
struct tNode* r;
};
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->d = data;
tNode->l = NULL;
tNode->r = NULL;

return(tNode);
}
void fillMat(struct tNode *root,int mat[][5],int count)
{
if(root==NULL)
return;

if((root->l!=NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
mat[root->d-1][(root->r)->d-1]=1;
}
else if((root->l!=NULL) && (root->r==NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
}
else if((root->l==NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->r)->d-1]=1;
}
else
{
return;
}
fillMat(root->l,mat,count);
fillMat(root->r,mat,count);
}
/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
int mat[5][5];
int i,j;

struct tNode *root = newtNode(1);
root->l = newtNode(2);
root->r = newtNode(3);
root->l->l = newtNode(4);
root->l->r = newtNode(5);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
mat[i][j]=0;
}
}
fillMat(root,mat,0);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
printf("%d",mat[i][j]);
}
printf("\n");
}
return 0;
}

Copy the predecessors of parent of the node and also mark parent as the predecessor of node

Assume node->val represents node ID in the matrix.


void mark_pred(tree *root, tree * parent, int *M)
{
if(root == NULL) return;
if(parent != NULL){
for (i=0; i < n; i++){
if(M[i][parent->val] == 1)
M[i][root->val = 1;
}
M[parent->val] [root->val] = 1;
}

mark_pred(root->left,root,M);
mark_pred(root->right,root,M);
}

I think pre order traversal should work. During pre order traversal, we can check node's left and right
child.
public void preOrder(Node root, Integer i, int[][] matrix){
if(root==null) return;
int parentIndex = i.intValue();
if(root.left() != null){
matrix[parentIndex][i++] = 1;
preOrder(root.left(), i, matrix);
}
if(root.right() != null){
matrix[parentIndex][i++] = 1;
preOrder(root.right(), i, matrix);
}
}

M = An nxn matrix initialized to all False

def pred(root, M):
  if root != None:
    # dfs
    pred(root.left, M)
    pred(root.right, M)
    row = M[root.data]
    row[root.data] = True # every node is in pred relationship with itself
    if root.left != None:
      row = row or M[root.left.data]
    if root.right != None:
      row = row or M[root.right.data]

public static int[][] predecessorMatrix(BinaryTreeNode<Integer> root, int n) {
		int[][] matrix = new int[n][n];
		dofindAncestorsOfNodes(root, matrix);
		return matrix;
	}
	
	private static void dofindAncestorsOfNodes(BinaryTreeNode<Integer> root, int[][] matrix) {

		if (root == null) {
			return ;
		}
		
		if (root.hasLeftChild()) {
			dofindAncestorsOfNodes(root.getLeft(),  matrix);
		}
		if (root.hasRightChild()) {
			dofindAncestorsOfNodes(root.getRight(),  matrix);
		}
		
		if (root.isLeafNode()) {
			return ;
		}
		
		if (root.hasLeftChild()) {
			matrix[root.getData()][root.getLeft().getData()] = 1;
			int[] row = matrix[root.getLeft().getData()];
			for (int i = 0; i < row.length; i++) {
				if (row[i] == 1) {
					matrix[root.getData()][i] = 1;
				}
			}
			
		}
		if (root.hasRightChild()) {
			matrix[root.getData()][root.getRight().getData()] = 1;
			int[] row = matrix[root.getRight().getData()];
			for (int i = 0; i < row.length; i++) {
				if (row[i] == 1) {
					matrix[root.getData()][i] = 1;
				}
			}
		}
	}

}