What would the complexity(Big O) of a function that calculates the sum of a specified node's subtree?
- husoskiLv 74 weeks ago
You visit every node in the subtree just once to get a value of to add to the sum, so with N nodes in the subtree it takes O(n) steps to perform the sum.
If N is the number of nodes in the whole tree, then the answer might depend on the shape of the tree. If you have a tree with (N-1) leaves, all descendants of the root, then once you have found a node the time to sum its subtree is O(1).