Friday, May 13, 2016

Number of ways to traverse an N-ary tree - GeeksforGeeks

Number of ways to traverse an N-ary tree - GeeksforGeeks
Given an n-ary tree, count number of ways to traverse an n-ary (or a Directed Acyclic Graph) tree starting from the root vertex.

`int` `calculateWays(Node * root)`
`{`
`   ``int` `ways = 1;  ``// Initialize result`

`   ``// If the tree is empty there is no way of traversing`
`   ``// the tree.`
`   ``if` `(root == NULL)`
`      ``return` `0;`

`   ``// Create a queue and enqueue root to it.`
`   ``queue<Node *>q;`
`   ``q.push(root);`

`   ``// Level order traversal.`
`   ``while` `(!q.empty())`
`   ``{`
`      ``int` `n = q.size();`
`      ``while` `(n>0)`
`      ``{`
`         ``// Dequeue an item from queue and print it`
`         ``Node * p = q.front();`
`         ``q.pop();`

`         ``// The number of ways is the product of`
`         ``// factorials of number of children of each node.`
`         ``ways = ways*(factorial(p->child.size()));`

`         ``// Enqueue all childrent of the dequeued item`
`         ``for` `(``int` `i=0; i<p->child.size(); i++)`
`            ``q.push(p->child[i]);`
`         ``n--;`
`      ``}`
`    ``}`

`   ``return``(ways);`
`}`