treetime-complexitydepth-first-search

if i have a tree such that there are n children and each children has another m children itself, how many times in total will i visit every node


for example: if i have a root with 30 children and each child has 35 children, how many times will I visit each node in total (including repeats) if I perform a depth first search?

I want to determine every path possible and I know that there are in total 30 * 35 total paths from root to leaf given my problem statement. However, I want to know how costly this is to calculate. So given a depth first search algorithm, how many times would you visit a node to calculate the total number of paths?

ie. imagine

root -> b -> c is 1 path total. and 3 nodes visited

root -> b -> d is 2 paths total and 5 nodes visited (since it backtracked to node b and visited d)


Solution

  • If you count backtracking to a node also as a visit, then you'll visit a leaf only once, but internal nodes are visited a first time and then after that as many times as they have children.

    • As the root node has 30 children, it will be visited 31 times.

    • As the 30 children of the root each have 35 children, they each get visited 36 times

    • Add to this the single visits to each of the leaves, i.e. 30 * 35

    In total that gives:

    31 + 30 * 36 + 30 * 35 = 2161 visits

    Another way to arrive at this number is to realise that each edge represents two node visits: a visit of the connected child, and a (re)visit of the connected parent. The initial visit of the root has to be added to this. So then you just count the number of edges, multiply by 2 and add 1:

    1 + (30 + 30 * 35) * 2 = 2161

    If we generalise, and the root has 𝑛 children and each child has 𝑚 children -- which are leaves, then we get:

    1 + 2(𝑛 + 𝑛𝑚) = 1 + 2𝑛(1+𝑚)