You are given the Ancestor matrix of a Binary tree, write an Algorithm to construct the corresponding tree.
For example, the below tree:
The order of rows in the above matrix is not defined. I have kept it in the ascending order because the data in our nodes is numeric and can be ordered.
Essentially, in the ancestor matrix, each node has a row and a column (may not be the same). The value at a[i][j] will be 1 iff node of Node representing j‘th column is the ancestor of node representing the i‘th row.
Write an algorithm that can construct the binary tree from a given Ancestor matrix.
Note: Since we don’t have information about whether a child is a left child or a right child, the tree which gets constructed will be unordered Binary tree(i.e, there can be max two children of a node but they will not be ordered as left or right).
- Add 1 more column in the matrix which contain the sum of all the elements in that row:
- Find the row, which has all zeros (for which sum[i] = 0). lets call this node r (root of the tree)
- Q.enqueue ( r);
- while (!Q.isempty)
- temp = Q.dequeue();
- remove both row & column of the temp node and update the sum column accordingly (ideally all the elements in the Sum column should decrease).
- Look for all the rows for which Sum[i] == 0
- add them as children to node temp.
- Insert them at the end of the queue.
The Algorithm will proceed as shown in the below diagram:
10 / \ 5 30
10 / \ 5 30 / \ 4 8