CODEWITHSUNDEEP
recursiondata-structurestime-complexity
Vitor de oliveira
Vitor de oliveira

Reputation: 113

The time complexity of count nodes in a binary tree with recursion, is a little more than o(n) correct?

Take this python code as an example

def count_nodes(node: Node):
if(node is None):
    return 0

return 1 + count_nodes(node.left) + count_nodes(node.right)

On the leafs, the recursion will point to left and right and return 0

Soo in a very big binary tree the time complexity will be:

o(n) + the number of leafs * 2

Is that correct?, or I am misunderstanding the idea of time complexity

Upvotes: 0

Views: 250

Answers (1)

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1529

In this example, you attached you are traversing only those nodes which are valid (or which exists), so in this case if you have n nodes you are traversing only n nodes.

It's no way wrong to write: o(n) + the number of leafs * 2 but eventually it would become: o(n) in terms of Big-O.

Upvotes: 1

Related Questions