CODEWITHSUNDEEP
time-complexity
Holden21200
Holden21200

Reputation: 23

Time Complexity Analysis of Recursive Tree Treversal Algorithm

I am supposed to design a recursive algorithm that traverses a tree and sets the cardinality property for every node. The cardinality property is the number of nodes that are in the subtree where the currently traversed node is the root.

Here's my algorithm in pseudo/ python code:

SetCardinality(node)
 if node exists:
   node.card = 1 + SetCardinality(x.left_child) + SetCardinality(x.right_child)
   return node.card
 else:
   return 0

I'm having a hard time coming up with the recurrence relation that describes this function. I figured out that the worst-case input would be a tree of height = n. I saw on the internet that a recurrent relation for such a tree in this algorithm might be: T(n) = T(n-1) + n but I don't know how the n in the relation corresponds to the algorithm.

Upvotes: 1

Views: 266

Answers (1)

Berthur
Berthur

Reputation: 4495

You have to ask yourself: How many nodes does the algorithm visit? You will notice that if you run your algorithm on the root node, it will visit each node exactly once, which is expected as it is essentially a depth-first search.

Therefore, if the rest of your algorithm is constant-time operations, we have a time complexity of O(n) for the total number of nodes n.

Now, if you want to express it in terms of the height of the tree, you need to know more about the given tree. If it's a complete binary tree then the height is O(logn) and therefore the time complexity would be O(2h). But expressing it in terms of total nodes is simpler. Notice also that the shape of the tree does not really matter for your time complexity, as you will be visiting each node exactly once regardless.

Upvotes: 1

Related Questions