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+𝑚)

- "Magically" avoiding segfault
- How to automatically create README.md markdown of directory tree listing
- SAPUI5: Show array of expanded entity Set as sub node in Tree
- Decoding a Message from a Text File - Javascript
- Finding leftmost nodes in every level of a tree
- How to calculate the time complexity of this recursive function
- Find the child of a specific until the 5th child in SQL Server
- Reorder newick tree for specific two samples to be closest
- Balanced Binary Tree Solution
- R: Merging Parts of a Graph Together
- Binary Tree creation in C
- Convert an array of objects into a deep tree array using Javascript
- How to get for each node the sum of the edge weights for children in a networkx tree
- Generate JSON-tree-object from table containing paths
- How to pull children array (with object) to parent if exceed max depth?
- What is the most efficient/elegant way to parse a flat table into a tree?
- TypeError: cannot unpack non-iterable TreeNode object
- Quiscence Search Performance
- Read instance for Associative Computations Tree
- How to implement a Treeview in a Razor Page
- Python nested loop not breaking out for level order tree traversal
- Time Complexity of traversing n-ary tree seems to have multiple correct answers, which is most correct?
- Expression Tree with List parameters
- find cousins in a binary tree
- How to convert Newick tree format to a tree-like hierarchical object?
- Python Tensorflow & Keras error | AttributeError: module 'tree' has no attribute 'flatten'
- Why use base classes for list/tree nodes in the C++ standard library?
- Updating an element with a given field within a tree-like structure in mongodb
- D3 Tree Layout Separation Between Nodes using NodeSize
- Recursive tree function traversal