Feb 022013

You are given the Ancestor matrix of a Binary tree, write an Algorithm to construct the corresponding tree.

For example, the below tree:

Will have the following ancestor Matrix

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 jth 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).


The row of the root node will have all zeros because there is no ancestor to the root node. We will use Queue to solve this problem. Let Q be the Queue with operations enqueue, dequeue and isEmpty

  1. Add 1 more column in the matrix which contain the sum of all the elements in that row:
  2. Find the row, which has all zeros (for which sum[i] = 0). lets call this node r (root of the tree)
  3. Q.enqueue ( r);
  4. while (!Q.isempty)
    1. temp = Q.dequeue();
    2. remove both row & column of the temp node and update the sum column accordingly (ideally all the elements in the Sum column should decrease).
    3. Look for all the rows for which Sum[i] == 0
    4. add them as children to node temp.
    5. Insert them at the end of the queue.

The Algorithm will proceed as shown in the below diagram:

Now we have the root node (10).. all the Nodes whose sum are zero will be children of this node. Hence the tree will look like:
/  \
5  30
10 will be dequeed from the queue and 5 & 30 are also inserted in the Queue.
Next element in the Queue (to be removed from Queue) will be 5. Remove the corresponding rows & columns and is sum value becomes zero corresponding to some nodes then insert them as child nodes of 5.
   /  \
  5    30
 / \
4   8
Also insert 4 & 8 in the Queue (and remove them from Matrix).
Repeat the same for 30. Then repeat the same for 4, 8 and other nodes.
Let me know if the above algo is not correct and you want the code for the same

  9 Responses to “Build binary tree from ancestor matrics”

Comments (9)
  1. Can anybody provide me code for this. at the following email imtiazahmad211@gmail.com

  2. can you provide me code for this ?

  3. The time complexity of the algorithm is O(n2) right??
    Is there any other efficient algorithm than this?

  4. Awesome

  5. Hi Kamal, doesnt step 1 (sum of values in the row) directly give us the level of each node. I assume this is a BST (else there will be no one unique solution) which we can use to leverage whether the children are left / right at each level.

    Or another train of thought was to just sort the nodes (inorder) and step 1 gives us the root. Inorder + root + BST => should be enough to reconstruct the tree

    What are your comments on the above?

    • Hi Sai,

      I have updated the post to make the algo more clear.. Step-1 gives us the information of which node is at which level.. but it does not give us any information about the parent child relationship (i.e Node 4 & 40 are at the same level, but their parent nodes are different)..

      To get the parent-child relation, we have to subtract the values of corresponding nodes..

      This algorithm is not for BST but any UN-ORDERED Binary tree.. It can very well be applied for tree where nodes data cannot be ordered.. The tree being unordered means, that whether a child is the left child or right child does not matter. Hence the two tree below are same

         A              A
        / \            / \ 
       B   C          B   C

      Since the tree may not necessarily be BST .. the example I have chosen may have confused you :)

  6. hi can i pls have d code for this?

 Leave a Reply



You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  • Facebook
  • Google+
  • Twitter
  • YouTube