Question

Suppose we do not maintainą, parent pointer in a binary search tree. What is the complexity of computing
predecessor and successor?
A.
Oo(log n) for balanced and unbalanced search trees
OO(n) for unbalanced search trees and Oſlog n) for balanced search trees
OO(n) for unbalanced search trees and O[log base 2*n) for balanced search trees
CO(n) for balanced and unbalanced search trees​

Answer 1

Answer:

1. The time complexity for a single search in a balanced binary search tree is O(log(n)) . Maybe the question requires you to do n searches in the binary tree, hence the total complexity is O(nlog(n)) . The worst case complexity for a single search in an unbalanced binary search tree is O(n)