Construct a binary tree from ancestor matrix

You are given a matrix M[n, n] for a tree with n nodes. In the given matrix M, M[i, j] is true iff node j is an ancestor of node i. Construct the tree from the given matrix.

For example, you are given below matrix.

1 2 3 4
1 0 1 1 0

2 0 0 1 0

3 0 0 0 0

4 0 1 1 0

You need to construct the below tree. In the constructed tree ancestor relationship should be correct. A node can come on left or right of its parent as you cannot determine this information from the ancestor matrix

Node numbers used in matrix are in bracket
5(3)
|
|
10(2)
/ \
/ \
12(1) 13(4)

Solution:

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

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
}Node;


typedef Node *Tree;

typedef struct Level
{
int data;
int level;
Node *node;
}Level;

int sortLevel(const void *a, const void *b)
{
const Level *x = a;
const Level *y = b;

return x->level - y->level;

}

/*
    constructs a binary tree from ancestor matrix
    returns NULL, if matrix is invalid
*/

Tree constructTreeFromAncestorMatrix(int n, int ancestors[n][n])
{
//Calculate level of each node (level is the num of ancestor nodes)
Level levels[n];

int i, j;

for(i = 0; i < n; i++)
{
levels[i].data = i;
levels[i].level = 0;

for(j = 0; j < n; j++)
levels[i].level += ancestors[i][j];
}

//sort nodes based on level
qsort(levels, n, sizeof(Level), sortLevel);


//first node level should be zero
if(levels[0].level != 0)
return NULL;

//Construct root node;
Tree t = (Node *)calloc(1, sizeof(Node));
t->data = levels[0].data;
levels[0].node = t;


//Link nodes to the ancestor in prev level
Node *node;

int prevLevelStart = 0;
int levelStart = 0;
int curlevel = 0;

for(i = 1; i < n; i++)
{
//allocate the node
node = (Node *)calloc(1, sizeof(Node));
node->data = levels[i].data;
levels[i].node = node;

//Check level change
if(curlevel != levels[i].level)
{
prevLevelStart = levelStart;
levelStart = i;
curlevel = levels[i].level;
}

//find the parent in prev level
for(j = prevLevelStart; j <levelStart; j++)
{
if(ancestors[levels[i].data][levels[j].data])
{
//attach to left or right based on free slot
Node *parent = levels[j].node;
if(!parent->left)
{
parent->left = node;
}
else if(!parent->right)
{
parent->right = node;
}
else //invalid binary tree
{
return NULL;
}

break;
}
}
}

return t;
}
void preorder(Tree t)
{
if(!t) return;

printf("%d\n", t->data);

preorder(t->left);
preorder(t->right);
}


int main()
{
int n;

scanf("%d", &n);


int matrix[n][n];

int i, j;

for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
scanf("%d", &(matrix[i][j]));


Tree t = constructTreeFromAncestorMatrix(n, matrix);

preorder(t);

}
Advertisements

One thought on “Construct a binary tree from ancestor matrix

  1. Hi: I am working on one homework assignment,to perform matrix operations in recursive manner using binary tree.I have to divide matrix into four parts and call them recursively. will you give me hint I will post my code here!!!Sakshi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s