CODEWITHSUNDEEP
time-complexitybig-o
Oscar
Oscar

Reputation: 568

What is the time complexity of finding the depth of a binary tree given my algorithm?

I want to find the depth of a node in a binary tree where the depth of the empty tree is defined as -1 and the depth of a node is defined as 1 greater than its parent.

Input is v

Output is the depth of v

Procedure Depth(v)
    if v = null then
        return −1
    return 1 + Depth(v.parent)

I am confused because the time depends on the size of the tree. Does that mean it is O(n)? Or is it O(1) because the size of the tree is a konstant? Or is it O(log(n)) because more than half of the elements of the tree are not being looped through? Please explain your answer because I am very confused right now.

Upvotes: 0

Views: 185

Answers (1)

Berthur
Berthur

Reputation: 4495

You need to think about which nodes are being visited by your algorithm. You will find that it is only the original node, its parent, its parent's parent etc. This is bounded by the height of the tree.

Now, if your binary tree is balanced, then its height is bounded by O(log n), where n is the number of nodes in your tree.

If it is not balanced, then for all you know, the nodes could all be stacked one above the other, giving you a bound of O(n).

Upvotes: 1

Related Questions