Interview Practice Questions: There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all

Interview Practice Questions: There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all

There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

Solution:

The below solution is O(n^2) solution. Each array entry is visited exactly once.

The basic idea is to make current node ancestor for all the nodes except for itself and it's own ancestors.

For any node, it's own ancestors  are maintained in set.
Pseudo code:

void fill(int[][] a,int n, Node root,Set<Integer> parents) {
     if(root == null)return;
     for(int j=0;j<n;j++) {
        if(!parents.contains(j) && j != root.value) {
                  a[root.value][j] = 1;
        }
     }
     parents.add(root.value);
     fill(a,n,root.left,parents);
     fill(a,n,root.right,parents);
     parents.remove(root.value);
}

Read full article from Interview Practice Questions: There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all