CareerCup

Do the BFS and update nodes position like This
Node Position = (parent position , current node position)
a ---- 0, 1
b ---- 1,2
c ---- 1,3
d ---- 1,2,4
e ---- 1,2,5
f ---- 1,3,6
g ---- 1,3,7

Now just ignore the last comma separated values for every node and complete the matrix as shown below

a  b  c  d  f  g

a  0  0  0  0  0  0

b  1  0  0  0  0  0

c  1  0  0  0  0  0

d  1  2  0  0  0  0

e  1  2  0  0  0  0

f  1  0  3  0  0  0

g  1  0  3  0  0  0

Finally replace all none zero number to 1.

Do DFS or BFS. Put 1 for all the nodes which are in the path from root-->current node other wise put 0 in the matrix.

Store a vector that holds the parent node values during DFS. When printing a node, set the corresponding entries in matrix to 1.

Path(node* root, vector<char> parents)
    {
           if(root == NULL) return;

            //Update Matrix for current node
            for(int i=0;i<parents.size();i++)
            {
               M[root->val][parents[i]] = 1;
            }

           
           parents.push_back(root->val);

           Path(root->left, parents);
           Path(root->right,parents);
    }

I think the below code can be optimized in a lot of ways. But the basic logic should be more or less the same.

public void ConstructMatrix(BinaryNode inpNode)
{
    if (null == inpNode)
    {
        return; 
    }

    List<NodeInfo> nodes = new List<NodeInfo>();
    nodes = this.ContructNodeInfoList(inpNode);
    Console.WriteLine();

    foreach (NodeInfo item in nodes)
    {
        Console.WriteLine(item.ToString());
    }

    int noOfNodes = nodes.Count;
    int[,] nodeMatrix = new int[noOfNodes, noOfNodes];
    int row, col;
    NodeInfo tempNodeInfo;

    foreach (NodeInfo nodeItem in nodes)
    {
        tempNodeInfo = nodeItem;
        row = nodeItem.nodePosition;
        while (tempNodeInfo.parentPosition >= 0)
        {
            col = tempNodeInfo.parentPosition == -1 ? 0 : tempNodeInfo.parentPosition;
            nodeMatrix[row, col] = 1;
            tempNodeInfo = nodes[tempNodeInfo.parentPosition];
        }
    }

    Console.WriteLine();
    Console.Write("  ");
    foreach (NodeInfo item in nodes)
    {
        Console.Write(item.treeNode.Value + " ");
    }
    Console.WriteLine();
    for (int i = 0; i < nodeMatrix.GetLength(0); i++)
    {
        Console.Write(nodes[i].treeNode.Value + " ");
        for (int j = 0; j < nodeMatrix.GetLength(1); j++)
        {
            Console.Write(nodeMatrix[i, j] + " ");
        }
        Console.WriteLine();
    }
}

private List<NodeInfo> ContructNodeInfoList(BinaryNode inpNode)
{
    if (null == inpNode)
    {
        return null;
    }

    List<NodeInfo> resultNodes = new List<NodeInfo>();
    int nodePosCounter = 0;
    int listIndex = 0;
    resultNodes.Add(new NodeInfo(inpNode, nodePosCounter, -1));

    while (listIndex < resultNodes.Count)
    {
        if (null != resultNodes[listIndex].treeNode.Left)
        {
            resultNodes.Add(new NodeInfo(resultNodes[listIndex].treeNode.Left,       ++nodePosCounter, resultNodes[listIndex].nodePosition));
        }

        if (null != resultNodes[listIndex].treeNode.Right)
        {
            resultNodes.Add(new NodeInfo(resultNodes[listIndex].treeNode.Right, ++nodePosCounter, resultNodes[listIndex].nodePosition));
        }

        listIndex++;
    }

    return resultNodes;
}

try this

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

int f[7][7] = {0};

struct node {
        //int val;
        char val;
        struct node *left;
        struct node *right;
};

void create(struct node ** root, int val){
        struct node *x;
        struct node *r = *root;
        x = (struct node*)malloc(sizeof(struct node));
        x->val = val;
        x->right = x->right = NULL;
        if(*root == NULL){
                *root = x;
        }
        else {
                if(val < r->val){
                        create(&(r->left),val);
                }
                else{
                        create(&(r->right),val);
                }
        }
}
void print_in(struct node *r){
        if(r!=NULL){
                print_in(r->left);
                printf("\t %c ", r->val);
                print_in(r->right);
        }
}

//matrix to be filled
void fill(struct node *parent, struct node *cur)
{       int i=0;
        if(cur != NULL){
                if(parent != NULL){
                        f[cur->val - 'a'][parent->val - 'a'] = 1;

                }
                fill(cur,cur->left);
                fill(cur,cur->right);
                if(parent != NULL){
                        for(i=0;i<7;i++){
                                if(f[i][parent->val-'a'] == 0){
                                        f[i][parent->val - 'a'] = f[i][cur->val - 'a'];
                                }
                        }
                }
        }
}


void main(){
        //int a[6] = {6,3,1,4,10,9};
        char a[7] = {'d','b','a','c','f','e','g'};
        int i = 0;
        int j =0;
        struct node *root = NULL;
        for(i=0;i<7;i++){
                create(&root,a[i]);
        }
        printf(" \n ");
        print_in(root);
        //printf("\n ");
        fill(NULL,root);
        for(i=0;i<7;i++){
                printf("\n %c ",'a'+i);
                for(j=0;j<7;j++){
                        printf("\t %d ",f[i][j]);
                }
        }
        printf("\n");


}

private static void translate(Node<Integer> node,int[][] matrix){
		if(node==null)
			return;
		else{
			translate(node.getLeft(),matrix);
			translate(node.getRight(),matrix);
			
			if(node.getLeft()!=null){
				for(int i=0;i<matrix.length;i++){
					if(matrix[i][node.getLeft().getData()]==1)
						matrix[i][node.getData()]=1;
				}
				matrix[node.getLeft().getData()][node.getData()] = 1;
			}
			if(node.getRight()!=null){
				for(int i=0;i<matrix.length;i++){
					if(matrix[i][node.getRight().getData()]==1)
						matrix[i][node.getData()]=1;
				}
				matrix[node.getRight().getData()][node.getData()] = 1;
			}
		}
	}

If the tree is always balanced then the generated matrix will always be the same ! We can figure out the algorithm and generate it. If the binary tree is not balanced then how is the matrix constructed, i.e., what constitutes the column and row labels ? Is it the order of the BFS ?

simple pseudo code/algo


parent [][]
node

fun(node)
parent[node->left->data][node] = 1
parent[node-right->data][node] = 1
parent[ndoe-right->data][root] = 1
parent[node-left->data][root] = 1
fun(node->left)
fun(node->right)


for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(!parent[i][j])
parent[i][j] = 0

DFSMARK(node p, node parent)
{
if(p == null) return;

if(parent != null)
{
A[parent->value][p->value] = 1;

DFSMARK(p->left, p);
DFSMARK(p->right, p);

for(int i = 0; i < rowsize, i++)
{
A[parent->value][i] |= A[p->value][i]
}
}
}

It is kind of postorder traversal and we update the parent column by ORing child columns and adding 1 on the two positions of child.
Please comment if I am missing something.

class MatrixFromTree
    {
        public static int[,] matrix;
        public static void Matrix(Node root, List<Node> list)
        {
            if (root == null)
                return;
            list.Add(root);
            Matrix(root.Left, list);
            Matrix(root.Right, list);
            list.Remove(list[list.Count-1]);
            for (int i = 0; i < list.Count; ++i)
            {
                Node parent = list[i];
                matrix[(int)(root.ID - 65), (int)(parent.ID - 65)] = 1;
            }
        }
        public static void Matrix(Node root, int row, int col)
        {
             List<Node> list=new List<Node>();
             matrix = new int[row, col];
             Matrix(root, list);
        }
    }