create ancestor matrix for binary tree

问题:

     1
   /  \
  2    3
 / \   / \
4   5 6   7

for the given binary tree we need to create a matrix a[7][7] satisfying the ancestor property like a[2][1]=1 since 1 is an ancestor of 2 ....

i solved it by using extra space an array ...the solution i came up is

int a[n][n]={0};
void updatematrix(int a[][n],struct node *root,int temp[],int index){

if(root == NULL)
  return ;
int i;

for(i=0;i< index;i++)
  a[root->data][temp[i]]=1;
temp[index]=root->data;

updatematrix(a,root->left,temp,index+1);
updatematrix(a,root->right,temp,index+1);
}

is there any mistake in my solution ? can we do this inplace ???(i mean without using the temp array )

回答1:

temp contains the path from root to current node, i.e. the set of nodes visited while walking down the tree to arrive at the current node.

If you have a parent pointer in each node (but I guess not), you can follow those pointers and walk up the tree to traverse the same set of nodes as temp. But this uses more memory.

You can also walk down the tree several times (pseudocode):

def updatematrix(a,node):
  if node is null: return
  walkDown(a.data,node.left)
  walkDown(a.data,node.right)
  updatematrix(a,node.left)
  updatematrix(a,node.right)

def walkDown(data,node):
  if node is null: return
  a[node][data] = 1
  walkDown(data,node.left)
  walkDown(data,node.right)

Same complexity, but the pattern of memory access looks less cache friendly.