Ancestor Matrix Problem.

There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

    /*  

          * IDEA is to use post-order traversal of a binary tree because in post-order we have child nodes first and then parent node which makes our task easy.

          * Algorithm of post order traversal is modified to return a string to calling function. 

          * This string contains all the child nodes of a tree separated by a space.

          * Process current node and add it to str then return str.

          * Pass str to setArray function and also current node.

          * Current node will be parent node and str will contain all child nodes of parent node separated by space.

          * Set arr[parentNode][childNode] = 1.

          * Scan str from left to right and add character to string ch, if space is encountered convert ch to integer and set arr[parent][ch] = 1.

          * Now set ch = “” and repeat.Press any key to continue . . .

    */

int **arr;

void setArray(string child, int parent)

{

     string ch ="";

     for(int i=0; i<child.length()-1; i++)

     {

             if(child[i] == ' ')

             {

                         if(ch != "")

                         {

                               arr[parent][toInt(ch)] = 1;

                         }

                         ch = "";

             }

             else

                         ch += child[i];

     }

}

string fillArray(node *ptr)

{

       string str ="";

       if(ptr)

       {

              str += " " + fillArray(ptr->getLeftChild());

              str += " " + fillArray(ptr->getRightChild());

              str += " " + toString(ptr->getData());

              setArray(str,ptr->getData());

       }

       else

           str = "";

       return str;

}

//Create and initializes 2-D array to all zeros.

void initializeArray(int n)

{

     arr = new int*[n+1];

     for(int i=0; i<=n; i++)

     {

             arr[i] = new int[n+1];

             for(int j=0; j<=n ; j++)

                     arr[i][j] = 0;

     }

}

//Diplay the 2-D array.

void displayArray(int n)

{

     for(int i=0; i<=n; i++)

     {

             cout<<"\n\nrow "<<i<<"\t";

             for(int j=1; j<=n ; j++)

             {

                     if( i ==0 )

                         cout<<" c"<<j;

                     else

                         cout<<"  "<<arr[i][j];

             }

     }

}

//Convert a string to integer and return int.

int toInt(string s)

{

    int num;

    istringstream st(s);

    st >> num;

    return num;

}

//Convert integer to string and return string.

string toString(int Number)

{

        string Result;          

        // stream used for the conversion

       ostringstream convert; 

       // insert the textual representation of 'Number' in the characters in the stream       

       convert << Number;     

        // set 'Result' to the contents of the stream

       Result = convert.str();

       return Result;

}

ORIGINAL TREE

                 6

               /   \

              2     8

             / \   / \

            1   4 7   9

               / \     \

              3   5     10

CHILD NODES OF A NODE  

1       ChildNodes :    1

3       ChildNodes :    3

5       ChildNodes :    5

4       ChildNodes :     3    5 4

2       ChildNodes :     1     3    5 4 2

7       ChildNodes :    7

10      ChildNodes :    10

9       ChildNodes :      10 9

8       ChildNodes :     7      10 9 8

6       ChildNodes :      1     3    5 4 2     7      10 9 8 6

Ancestor Matrix

row 0    c1 c2 c3 c4 c5 c6 c7 c8 c9 c10

row 1     0  0  0  0  0  0  0  0  0  0

row 2     1  0  1  1  1  0  0  0  0  0

row 3     0  0  0  0  0  0  0  0  0  0

row 4     0  0  1  0  1  0  0  0  0  0

row 5     0  0  0  0  0  0  0  0  0  0

row 6     1  1  1  1  1  0  1  1  1  1

row 7     0  0  0  0  0  0  0  0  0  0

row 8     0  0  0  0  0  0  1  0  1  1

row 9     0  0  0  0  0  0  0  0  0  1

row 10    0  0  0  0  0  0  0  0  0  0