Build binary tree from ancestor matrics

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.

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 an 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

 10
/  \
5  30

    10
   /  \
  5    30
 / \
4   8

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

1. A 2-dim array representing the ancestor matrix. This matrix has one extra column for sum.
2. 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.
3. A struct Node, representing the structure of the Node in a Binary tree.
4. 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, let’s look at some of the helper functions.
The below function will set up the initial sum values for each row of the matrix. The sum column will represent the 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];
    }
}

The above function is to be called only once before the main logic. It will set the last column of the matrix correctly. 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

Now, 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 in 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;
}