What would the complexity(Big O) of a function that calculates the sum of a specified node's subtree?

And why?

1 Answer

  • 4 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).

Still have questions? Get your answers by asking now.