CODEWITHSUNDEEP
algorithmrecursion
Kris
Kris

Reputation: 59

Finding time complexity with trees and recursion

Am I right in thinking this is O(n)? I'm really bad at recursion. Could someone please confirm, or explain to me?

Counter(a)
    if hasLeft(a)
        return Counter(left(a) + Counter (right(a))
    else
        return 1

Basically, if there isn't a left node in the tree, it returns 0. If there are left notes, it returns 1.

Thanks!

Upvotes: 2

Views: 1267

Answers (2)

Saeed Amiri
Saeed Amiri

Reputation: 22555

If it's (binary) tree, because there isn't any loop in graph, it just check each node at most one time so it's O(n).

Upvotes: 1

Jim Mischel
Jim Mischel

Reputation: 133975

Your code doesn't do what's advertised. You said you want it to return 1 if there is a left node, and 0 if there is not a left node. But your code is:

Counter(a)
    if hasLeft(a)
        return Counter(left(a)) + Counter(right(a))
    else
        return 1

This returns 1 if there is no left node at the root, but it doesn't check the rest of the tree. This code will not examine the entire tree, but rather will stop at the first level that has no left node.

What are you really trying to do?

Upvotes: 1

Related Questions