## Sunday, April 17, 2016

### Construct Ancestor Matrix from a Given Binary Tree - GeeksforGeeks

Construct Ancestor Matrix from a Given Binary Tree - GeeksforGeeks
Given a Binary Tree where all values are from 0 to n-1. Construct an ancestor matrix mat[n][n]. Ancestor matrix is defined as below.
`mat[i][j] = 1 if i is ancestor of j  mat[i][j] = 0, otherwise  `

The idea is to traverse the tree. While traversing, keep track of ancestors in an array. When we visit a node, we add it to ancestor array and consider corresponding row in adjacency matrix. We mark all ancestors in its row as 1. Once a node and all its children are processed, we remove the node from ancestor array.
`// Creating a global boolean matrix for simplicity`
`bool` `mat[MAX][MAX];`

`// anc[] stores all ancestors of current node.  This`
`// function fills ancestors for all nodes.`
`// It also returns size of tree.  Size of tree is`
`// used to print ancestor matrix.`
`int` `ancestorMatrixRec(Node *root, vector<``int``> &anc)`
`{`
`    ``/* base case */`
`    ``if` `(root == NULL) ``return` `0;;`

`    ``// Update all ancestors of current node`
`    ``int` `data = root->data;`
`    ``for` `(``int` `i=0; i<anc.size(); i++)`
`       ``mat[anc[i]][data] = ``true``;`

`    ``// Push data to list of ancestors`
`    ``anc.push_back(data);`

`    ``// Traverse left and right subtrees`
`    ``int` `l = ancestorMatrixRec(root->left, anc);`
`    ``int` `r = ancestorMatrixRec(root->right, anc);`

`    ``// Remove data from list the list of ancestors`
`    ``// as all descendants of it are processed now.`
`    ``anc.pop_back();`

`    ``return` `l+r+1;`
`}`

`// This function mainly calls ancestorMatrixRec()`
`void` `ancestorMatrix(Node *root)`
`{`
`    ``// Create an empty ancestor array`
`    ``vector<``int``> anc;`

`    ``// Fill ancestor matrix and find size of`
`    ``// tree.`
`    ``int` `n = ancestorMatrixRec(root, anc);`

`    ``// Print the filled values`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``for` `(``int` `j=0; j<n; j++)`
`            ``cout << mat[i][j] << ``" "``;`
`        ``cout << endl;`
`    ``}`
`}`