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

CodePudding user response：

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.