# Construct a Binary Tree from Ancestor Matrix

Given an ancestor matrix, whose cell (i, j) has value true if i is ancestor of j in a binary tree, construct a binary tree from it where binary tree nodes are labelled from 0 to n-1 where n is the size of the ancestor matrix.

Please note that there maybe several binary trees constructed out of a single matrix since ancestor matrix doesn’t specify that which child is left and which is right.

For example,

Input:

0 0 0 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 0 0
1 1 1 1 0

Output:

Any one of the below trees

4              4             4
/    \           / \          /   \
1      2   OR   2    1    OR  1     2  OR ….
/     /         /      \        \    /
0     3         3        0        0  3

We start by creating an array of pointers to store the binary tree nodes. Since the number of set values in i’th row indicates number of descendants of node i, we store row numbers that correspond to a given count in a multimap. We then process the multimap entries in sorted order (smallest value first) and for each entry, we assign a new node against current row in the array. If it is non-leaf node (having non-zero value), we set left/right child of it to its descendants nodes whose parent are not set (there can be at-max two such node if given ancestor matrix is correct). Finally, we return the last processed node, which has maximum value and would be root of the binary tree.

C++ implementation –

Output:

0 1 4 3 2

(1 votes, average: 5.00 out of 5)