recategorized by
2,376 views
3 votes
3 votes
Suppose we do not have a parent pointer in the nodes of a search tree, only left-child and right-child. Which of the following operations can be computed in time $O(\log n)$ for a balanced search tree?

1- find, insert, delete, but not min, max, pred, succ
2- find, insert, delete, min, max, but not pred, succ
3- find, insert, delete, pred, succ but not min, max
4- All of find, insert, delete, min, max, pred, succ
recategorized by

3 Answers

Best answer
5 votes
5 votes
Balanced search tree so height is O(logn) having n elements.

min and max is easy to find...

For min just start with root and traverse left until u don't get null ... When u get null that is min element..O(logn)

Same for max traverse Right until you get null that is max element.O(logn)

Insert , delete and find too take O(log).

Now for predecessor : suppose key is given then jump to the left child of key and find the descendent right node that is predecessor of given key..which takes O(logn)

Successor : jump to the right child and find left descendent of it that is successor of given key. Which also takes O(log) time.

So ans should be D.
selected by
1 votes
1 votes
Say tree is Binary search tree. Here we donot have parent pointer. So, to find a node we have to do by level order traversal.  Binary search tree can be visited in O(log N) time when we visit a node from root to leaf. But in level order traversal we have to visit all nodes So, it will take O(N) time.

Now, in worst case ,if the tree is skewed tree and for min, max we take O(N) and O(1) time . To find predecessor , successor also takes O(N) time
Answer:

Related questions

4 votes
4 votes
4 answers
1
Parshu gate asked Nov 27, 2017
6,669 views
How many different binary search trees can be constructed using six distinct keys? 256 128 132 264
1 votes
1 votes
1 answer
2
pradeepchaudhary asked Aug 19, 2018
19,111 views
8. What are the worst case and average case complexities of a binary search tree?a) O(n), O(n)b) O(logn), O(logn)c) O(logn), O(n)d) O(n), O(logn)
6 votes
6 votes
3 answers
4
air1ankit asked Mar 9, 2017
1,593 views
I/p - array of n element in which untill some postion all are integer and afterward all are star (*) O/p- find the postion of 1st star (*)Hint - if lenear search is possi...