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

Solution:

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:
 10
/  \
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.
    10
   /  \
  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
pinkdiamonds.nl

  8 Responses to “Build binary tree from ancestor matrics”

Comments (8)
  1. can you provide me code for this ?

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

  3. Awesome

  4. 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 :)

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

 Leave a Reply

(required)

(required)

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=""> <strike> <strong>

  • Facebook
  • Google+
  • Twitter
  • YouTube