# Interview Questions

# Build binary tree from ancestor matrics

- February 2, 2013
- Posted by: Kamal Rawat
- Category: Algorithms

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

### Solution:

- 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

### Code

Since I am getting lot of request to write code for this here is the code. We are using the same logic as above, just that since the physical removal of rows from an array is costly, we just mark the rows as removed.

**Data structure used**

- A 2-dim array representing the ancestor matrix. This matrix has one extra column for sum.
- A one-dim Array representing the original values (which are the actual numbers that will be inserted in the tree). This may be a character array if tree nodes are character values.
- A struct Node, representing the structure of the Node in a Binary tree.
- Some constant values

// Constant values used #define N 7 #define REMOVED -1 #define NO_VALUE_FOUND -2 // Node of a Tree struct Node { int data; Node* lptr; Node* rptr; Node(char value): data(value), lptr(NULL), rptr(NULL){} }; // Values of the nodes in the tree int nodeName[N] = { 1, 4, 5, 8,10,30,40}; // Last column is for sum int ancestorMat[N][N+1]={ { 0, 1, 1, 0, 1, 0, 0, 0 }, { 0, 0, 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 1, 0, 0 }};

With the data structure in place, lets look at some of the helper function.

The below function will set up the initial sum values for each row of the matrix. The sum column, will represent total number of ancestors the value has.

// Calculate the sum first time void calculateInitialSumAndRemoveRoot() { for(int i=0; i<N; i++) { ancestorMat[i][N] = 0; for(int j=0; j<N; j++) ancestorMat[i][N] += ancestorMat[i][j]; } }

Above function is to be called once once before the main logic. It will set the last column of the matrix correct. After the function is called, values in the matrix will be

0 1 1 0 1 0 0 3 0 0 1 0 1 0 0 2 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 2

At this point we will remove the row with zero sum value. We will not physically remove the row, but just mark the row as removed. The below function look for the first row, whose sum is zero and mark it removed and return the value for that row (remember value is is different array)

int findAndRemoveFristZeroElement() { for(int i=0; i<N; i++){ if(ancestorMat[i][N] == 0) { ancestorMat[i][N] = REMOVED; return nodeName[i]; } } return NO_VALUE_FOUND; // NO MORE NODE }

Then we need a function which will decrement the sum values from the matrix, When a row is removed, all its children’s sum value will be decremented

void decrementParentCountForNode(int value) { for(int j=0; j<N; j++) { if(nodeName[j] == value) { for(int i=0; i<N; i++) { if(ancestorMat[i][j] == 1) ancestorMat[i][N]--; } return; } } }

Now let us come to the main function, This function find the root element, remove it and create the root node of the tree and then call the recursive function to build rest of the tree.

Node* convertMatToTree() { // compute the sum column first time. calculateInitialSumAndRemoveRoot(); // Find value of the root node of the tree. // and remove it from matrix int rootValue = findAndRemoveFristZeroElement(); // If there is no root node then return if(rootValue == NO_VALUE_FOUND){ return NULL; } // If there is a root node then make tree. Node* root = new Node(rootValue); // Create rest of the tree and set the // values in left and right child of root convertMatToTreerecursive(root); return root; }

Now the only function left is the one which does the work recursively, Here is that function.

void convertMatToTreerecursive(Node* root) { if(root == NULL){ return; } // decreasing the sum count for children of root. decrementParentCountForNode(root->data); // Finding first child and setting it as left child int value = findAndRemoveFristZeroElement(); if(value != NO_VALUE_FOUND){ root->lptr = new Node(value); } // Finding second child and setting it as right child value = findAndRemoveFristZeroElement(); if(value != NO_VALUE_FOUND){ root->rptr = new Node(value); } // If there is a left child create the left tree if(root->lptr != NULL) convertMatToTreerecursive(root->lptr); // If there is a right child create the right tree if(root->rptr != NULL) convertMatToTreerecursive(root->rptr); }

Below is the complete working code (with the main function)

#define N 7 #define REMOVED -1 #define NO_VALUE_FOUND -2 struct Node { int data; Node* lptr; Node* rptr; Node(char value): data(value), lptr(NULL), rptr(NULL){} }; int nodeName[N] = { 1, 4, 5, 8,10,30,40}; // Last column is for sum int ancestorMat[N][N+1]={ { 0, 1, 1, 0, 1, 0, 0, 0 }, { 0, 0, 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 1, 0, 0 }}; // Calculate the sum first time void calculateInitialSumAndRemoveRoot() { for(int i=0; i<N; i++) { ancestorMat[i][N] = 0; for(int j=0; j<N; j++) ancestorMat[i][N] += ancestorMat[i][j]; } } int findAndRemoveFristZeroElement() { for(int i=0; i<N; i++){ if(ancestorMat[i][N] == 0) { ancestorMat[i][N] = REMOVED; return nodeName[i]; } } return NO_VALUE_FOUND; // NO MORE NODE } void decrementParentCountForNode(int value) { for(int j=0; j<N; j++) { if(nodeName[j] == value) { for(int i=0; i<N; i++) { if(ancestorMat[i][j] == 1) { ancestorMat[i][N]--; } } return; } } } void convertMatToTreerecursive(Node* root) { if(root == NULL){ return; } // decreasing the sum count for children of root. decrementParentCountForNode(root->data); // Finding first child and setting it as left child int value = findAndRemoveFristZeroElement(); if(value != NO_VALUE_FOUND){ root->lptr = new Node(value); } // Finding second child and setting it as right child value = findAndRemoveFristZeroElement(); if(value != NO_VALUE_FOUND){ root->rptr = new Node(value); } // If there is a left child create the left tree if(root->lptr != NULL) convertMatToTreerecursive(root->lptr); // If there is a right child create the right tree if(root->rptr != NULL) convertMatToTreerecursive(root->rptr); } Node* convertMatToTree() { // compute the sum column first time. calculateInitialSumAndRemoveRoot(); // Find value of the root node of the tree. // and remove it from matrix int rootValue = findAndRemoveFristZeroElement(); // If there is no root node then return if(rootValue == NO_VALUE_FOUND){ return NULL; } // If there is a root node then make tree. Node* root = new Node(rootValue); // Create rest of the tree and set the // values in left and right child of root convertMatToTreerecursive(root); return root; } // Helper function to pring the matrix void printMat() { cout<<endl<<endl; for(int i=0; i<N; i++){ for(int j=0; j<=N; j++) cout<<ancestorMat[i][j]<<" "; cout<<endl; } } // Helper function to print the tree in PreOrder void preOrder(Node* r) { if(r==NULL){return;} cout<data << " "; preOrder(r->lptr); preOrder(r->rptr); } // Helper function to print the tree in InOrder void inOrder(Node* r) { if(r==NULL){return;} inOrder(r->lptr); cout<data << " "; inOrder(r->rptr); } int main() { printMat(); Node* root = convertMatToTree(); cout<<"Inorder Traversal of tree: "; inOrder(root); cout<<"\nPreOrder Traversal of tree: "; preOrder(root); return 0; }

Hi Kamal ,

Is it not possible to have a adjacency list having space complexity O(V+E) instead of adjacency(ancestor) matrix of

space 0(V^2) .In adjacency list , the look up function to check whether there is a edge from u to v requires O(V) time ,

but in adjacency(ancestor) matrix the same can be done in O(1) constant time .

Please provide your suggestion

Hi PrasunM, First of all the ancestor matrix is part of the question. So we can’t change it.

Usually graphs are represented using either Adjacency List or matrix.. So, we can apply the same here as well (tree is a acyclic-connected graph), but there are few points:

– The constant factor of list is big (because we are also storing one pointer for each node). So it’s not that we are storing very less memory. For a tree with few noted, the list may end up taking more memory.

– Since we are storing just 0’s and 1’s in the matrix, it can be further optimized to store one BIT (rather than sizeof(int)) memory for each cell.

– Another advantage is as you pointed out. The time.

Hi Akhlak, Please find the code now. http://www.ritambhara.in/build-binary-tree-from-ancestor-matrics/

Algorithm is correct but the performs some useless things.

Specifically, in steps 4b and 4c, you don’t really need to delete rows or columns from the matrix. All that is needed (instead of steps 4b & 4c) is to check which nodes have the currect node (“temp”) as their ancestor by checking the ancestor column for each row, and decrementing the sum column (which is actually just a separate array) accordingly. When a sum is decremented to zero (meaning that the current “temp” node is its last remaining ancestor, so it is the parent), then we add the node to the queue.

The loop is repeated once for each node, and in each loop iteration we scan one column of the matrix, so the complexity is O(N^2) which is optimal since this is the size of the input that needs to processed.

This is write.. when we write code, we don’t actually delete the row/column (because that is a very expensive operation).. If array is on the stack then it may not be possible also.. But it is easy to understand when we explain things like this.. good point anyway..

Can anybody provide me code for this. at the following email imtiazahmad211@gmail.com

The post is updated with code. Thanks.

can you provide me code for this ?

The post is updated with code. Thanks!

The time complexity of the algorithm is O(n2) right??

Is there any other efficient algorithm than this?

Awesome

Thanks Prasad

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

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

hi can i pls have d code for this?

will try to put it in few days.. why don’t you try it out and put it in the comment or mail to me. 🙂

Hi, the post is updated with code now. thanks!