A tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary search tree.

Problem:

A tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary search tree.

Solution:

Iterate over the array A and build array P, such that P[i] = # ancestor of node i. Thus, sum of A[i][j] for 0<=j<n

This will take O(n^2) time. While building the array P, keep track of node for which P[i] is 0. Certainly there can be only 1 such element i.e. root of the binary tree.

Now Node [0..i-1] will be in left sub tree of root and Node [i+1...n-1] will be right sub tree of root.

There can be only one node in 0..i-1 for which P[i] is 1, that will be root of left sub tree. Similar hold true for Nodes i+1...n-1. let index of node for which  P[j] is 1, 0<=j<=i-1, be k.

Node 0..k-1 will be in left sub tree of Node k which is left child of Node i. we need to find node x, 0<=x<=k-1 for which P[x] is 2. Hence we keep building our binary search tree.

Pseudo code

for i in 0..n-1
  p[i] = 0;
  for j in 0..n-1
     p[i] += a[i][j];
  return buildTree(p,0,n-1,0)

Node buildTree(int[] a,int left,int right,int rootIndex)
         for i in left...right
             if a[i] == rootIndex
                   Node root = new Node(i)
                   root.left = buildTree(a,left,i-1,rootIndex+1)
                   root.right = buildTree(a,i+1,right,rootIndex+1)
                   break;
          return root

The worst case complexity of this solution will be O(n^2) + O(n^2) which is O(n^2).
For average cases, where the binary tree is balanced complexity will be O(n^2) + O(n log n). This will be still be O(n^2) however second step will be faster in this case.