PTN
Reputation: 1692
Total number of nodes in a tree given number of branch and depth
Is it correct that the number of nodes in a tree, given maximum branching factor b and maximum depth d is O(b^d)?
I'm practicing some backtracking problems and trying to analyze the run time complexity of the solution, which traverses through all nodes in the "backtracking tree"
Upvotes: 0
Views: 1293
Answers (1)
Pixel
Reputation: 101
Yes, the maximum number of nodes will be b^d (b on first level, then b*b on level 2, etc d time), but the actual number of nodes may vary if the tree is not full. For maximum analysis of complexity that is a correct assumption however.
Upvotes: 1
Related Questions
- What is the time complexity of finding the depth of a binary tree given my algorithm?
- Counting number of nodes in a complete binary tree
- The time complexity of count nodes in a binary tree with recursion, is a little more than o(n) correct?
- Why is time complexity of recursive tree equal to number of leaf nodes instead of total number of nodes?
- Counting the number of Nodes in Binary Tree O(logn)^2
- Counting the depth of a tree using recursion
- Time Complexity for the given Tree Recursion problem
- time complexity of Print all nodes from root to leaves
- Count nodes in each subtree
- Time complexity of recursion-tree