CareerCup

Maintain a vector of nodes seen so far as we recursively visit the tree. In C++:

struct Node
{
    int value;
    Node* left;
    Node* right;
};


void visit(Node* n, std::vector<int>& v)
{
    if (n)
    {
        for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i)
        {
             matrix[*i][n->value] = 1;
        }
        v.push_back(n->value);
        visit(n->left, v);
        visit(n->right, v);
        v.pop_back();
    }
}

summing up each post to answer :) just intelligent pre-order traverse insert in the array 1 for the node you travel (parent will be available) so you get the array with 1 incase of parents ...

find transitive closure of the matrix thats the answer

Nice Algo!!!

will someone explain the code a bit...will be better for others to get the hang of whats going on..
thank you.

[1] Do a pre-order traversal and make an array
[2] for this array (assuming the index starts from 1) for each element at position k the elements at 2k and 2k+1 are its children. hence mark a[k][2k] = 1 and a[k][2k+1] = 1

not only a[k][2k] and a[k][2k+1] shud be marked as 1. The question says "ancestors" and not just "parents".
so a[k][2k],a[k][2k+1],a[k][4k],a[k][4k+1].. shud be marked 1.

Question doesn't mention that it has to be a binary tree.

simply do dfs and keep the ancestor element in the stack ......and fill the matrix with the stack element....

I think pre order makes too many assumptions ... I would go for the DFS method

Dunno why ppl dont read the question carefully ... it does not say a binary tree. I suppose we shall write code for an Nary tree.

Can u give an example?