CareerCup

1. Create a nxn matrix and initialize to -1
2. Normalize the key values, e.g., if the inorder traversal of the nodes are 377, 11, 5, 1055, 3, 8, ... then map them integers starting from 0 to n, (377, 0), (11, 1), (5, 2), (1055, 3), (3, 4), (8, 5), .... You can map the tree nodes instead of keys to integers too, i.e., Instead of HashMap<Integer, Integer>, you can use HashMap<TreeNode, Integer>.
3. Traverse the tree and set the matrix value for the parent

Note that, you can use any tree traversals, inorder, preorder, or postorder, for step 2 and 3.

here is the recursive preorder implementation

// initial call
ancestorMatrix(root, null, m, map);

public static void ancestorMatrix(TreeNode node, TreeNode parent, int[][] m, Map<Integer, Integer> map) {
	if (node == null) return;
		
	if (parent != null) m[map.get(node.data)][map.get(parent.data)] = parent.data;
		
	ancestorMatrix(node.left, node, m, map);
	ancestorMatrix(node.right, node, m, map);
}

The time complexity is O(n).

Assuming
a) NodeNum(node->left) = 2 * NodeNum(node) and
b) NodeNum(node->right) = 2 * Nodeum(node) + 1 and
c) the node can be ancestor of itself

1) initialize array to 0s.

2) a routine below

void updatematrix(bst *root, unsigned int N)
{
unsigned int i = N;
if (root == NULL)
return;
while (i != 0)
{
array[i-1][N-1] = 1;
i = (i >> 1);
}
updatematrix(root->left, 2*N);
updatematrix(root->right, 2*N+1);
}

The ancestor matrix can be calculated as below. You can test the below code:

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

typedef struct node node_t;
struct node
{
    int data;
    node_t *left;
    node_t *right;
};
node_t *newNode(int data)
{
    node_t *nn=(node_t *)malloc(sizeof(node_t));
    nn->data=data;
    nn->left=NULL;
    nn->right=NULL;
    return nn;
}

void findAncestor(node_t *root,int arr[][4],int temp[],int index)
{
    if(root==NULL)
        return;
    int i;
    for(i=0;i<index;i++)
          arr[root->data][temp[i]]=1;
    temp[index]=root->data;
    findAncestor(root->left,arr,temp,index+1);
    findAncestor(root->right,arr,temp,index+1);
}
int main()
{
    node_t *nn=newNode(1);
    nn->left=newNode(2);
    nn->right=newNode(3);
    int temp[4],i,j;
    int arr[4][4]={0};
    findAncestor(nn,arr,temp,0);
    printf("The ancestor matrix is\n");
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
        {
            if(arr[i][j]==1)
                printf("The ancestor of %d is %d ",i,j);
        }
}

Can someone tell what is ancestor Matrix?

I think the question could have been made clearer and the solution would depend on the requirements.
1. If the ancestor matrix is built sparsely, then determining whether a given node is an ancestor of another node would take O(n) time on avg.
2. If the matrix is built densely, then determining whether a given node is an ancestor of the other would take constant time.

Both sparse and dense matrices can be built recursively in a top-down fashion. To build a sparse matrix we will just mark the position of the parent node in the row of the child node.
To build a dense matrix we will have to copy the whole row of the parent node to the row of the child node and also mark the position of the parent node.

buildAncestorMatrix(Node childSubtree, Node parent) {

if (parent == null) do-nothing;

1. Copy the row of the parent to the row of the child
2. Mark parent as ancestor in the row of the child

if (childSubtree.leftSubtree != null)
     buildAncestorMatrix(childSubtree.leftSubtree, childSubtree);
if (childSubtree.rightSubtree != null)
	buildAncestorMatrix(childSubtree.rightSubtree, childSubtree);
}

If it is a bst, then:
1. In-order traversal of the tree to find the sorted array of node's elements, say arr. Then,

ancestor[n-1]=-1;
for(i=0;i<n-1;i++)
  ancestor[a[i]]=a[i+1]; //we would like to make a Matrix[n][n], then we get Ancestor[a[i]][a[i+1]]=1 (Ancestor Matrix is initialized to zero for all its entries).

This can be done in O(n).

if would like to have a new field in our structure, say ancestor, for every node, then:
1.Store the addresses of the nodes in their in-order traversal in an array, say arr.
2.

arr[n-1]->ancestor=NULL;
for(i=0;i<n-1;i++)
  arr[i]->ancestor=arr[i+1];

However, if the tree is NOT a binary tree, we can use the following (it is O(n^2) though):

void Ancestors(int val, struct bst *b, struct bst **cur)
{
	if(b)
	{
		if(b->data>val && ((*cur)==NULL || (*cur)->data>b->data))
			(*cur)=b;

		Ancestors(val,b->lc,cur);
		Ancestors(val,b->rc,cur);
	}
}
void FindAncestor(struct bst *b, struct bst *root)
{
	if(b)
	{
		struct bst *cur=NULL;
		Ancestors(b->data,root,&cur);
                b->ancestor=cur
		FindAncestor(b->lc,root);
		FindAncestor(b->rc,root);
	}
}

public void UpdateAncestorMatrix(Matrix m, TreeNode t, int parent)
{
	if (t == null)
		return;

	if (parent > 0)
	{
		for (int i = 0;i < m.GetLength(1); i++)
		{
			m[t.Value, i] = m[parent, i];
		}

		m[t.Value, parent] = 1;
	}

	UpdateAncestorMatrix(m, t.Left, t.Value);
	UpdateAncestorMatrix(m, t.Right, t.Value);
}

public class BinaryTreeAncestorMatrix {
	private class Node {
		int value;
		Node left;
		Node right;
		
		public Node(int val) {
			value = val;
			left = null;
			right = null;
		}
	}
	Node root = null;
	
		private void createAncestorMatrix(Node currNode, Node parent, int[][] ancestorMatrix, ArrayList<Integer> nodes) {
		if(currNode == null) return;
		if(currNode != null && parent == null) {
			nodes.add(currNode.value);
			createAncestorMatrix(currNode.left, currNode, ancestorMatrix, nodes);
			createAncestorMatrix(currNode.right, currNode, ancestorMatrix, nodes);
		}
		else {
			nodes.add(currNode.value);			
			for(int i = 0 ; i < ancestorMatrix[nodes.indexOf(parent.value)].length; i++) 
				ancestorMatrix[nodes.indexOf(currNode.value)][i] = ancestorMatrix[nodes.indexOf(parent.value)][i];
			ancestorMatrix[nodes.indexOf(currNode.value)][nodes.indexOf(parent.value)] = 1;
			createAncestorMatrix(currNode.left, currNode, ancestorMatrix, nodes);
			createAncestorMatrix(currNode.right, currNode, ancestorMatrix, nodes);
		}
	}

	createAncestorMatrix(root, null, ancestorMatrix, nodes);

}