Construct Binary Tree From Ancester Matrix Efficiently

You are given a matrix M[n, n] for a tree with n nodes. In the given matrix M, M[i, j] is true iff node j is an ancestor of node i. Construct the tree from the given matrix.

For example, you are given below matrix.

1 2 3 4
1 0 1 1 0

2 0 0 1 0

3 0 0 0 0

4 0 1 1 0

You need to construct the below tree. In the constructed tree ancestor relationship should be correct. A node can come on left or right of its parent as you cannot determine this information from the ancestor matrix

Node numbers used in matrix are in bracket
5(3)
/
/
10(2)
/ \
/ \
12(1) 13(4)


Data Structure Used: 2-D Array , Binary Tree

Algorithm


Time Complexity
Space Complexity