State and explain the worst case big O complexity of the recursive algorithms of

Question

State and explain the worst case big O complexity of the recursive algorithms of the binary search tree shown below. (Code is in python)

Comment: Without proof, briefly explain in English.

A)
def numberOfNodes(r):
counter=1
if r == None:
return 0
else:
counter +=numberOfNodes(r.left)
counter +=numberOfNodes(r.right)
return counter

B)
def treeHeight(r):
if r == None:
return 0
lheight = treeHeight(r.left)
rheight = treeHeight(r.right)
if (lheight > rheight):
return lheight + 1
else:
return rheight + 1

C)
def numberOfLeaves(r):
if r == None:
return 0
if (r.left == None and r.right == None):
return 1
else:
return numberOfLeaves(r.left) + numberOfLeaves(r.right)

Explanation / Answer

A)
numberOfNodes(N)
In this function the Pointer moves to left Subtree and Right Subtree until all the nodes are Visited , So we have maximum N nodes SO the Big Oh Complexity is O(N)

B)
treeHeight(N)
In this function the Pointer moves to left Subtree and Right Subtree until all the nodes are Visited , So we have maximum N nodes SO the Big Oh Complexity is O(N)

C)
numberOfLeaves(N)
In this function the Pointer moves to left Subtree and Right Subtree until all the nodes are Visited , So we have maximum N nodes SO the Big Oh Complexity is O(N)

Thanks, let me know if there is any concern/doubts

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.