Author: Ankur Verma
Tester: Raju Varshney
Graphs, Depth First Search
Given a rooted tree, find the number of ways to traverse the tree, starting from the root.
The number of ways is the product of factorials of number of children of each node.
First, it must be noticed that since every node is reachable from every other node and there are N - 1 edges, the graph is a tree.
Let some Parent node be P and its children be C_1, C_2, C_3, … , C_n, then:
ways(P) = n!
This is because, after P is visited, its children will be visited in some order - the number of ways to order the children would be factorial of the number of children of P.
Hence, by the counting principle, the total number of ways to traverse the tree would be =
children(1)! * children(2)! * … * children(N)!
where children(X) represents the number of children of node X in the rooted tree.