GATE CSE
First time here? Checkout the FAQ!
x
0 votes
227 views
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
asked in Algorithms by Veteran (35k points)   | 227 views

3 Answers

+4 votes
Best answer
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.
answered by Veteran (21.3k points)  
selected by
If you are talking about predecessor and successor in the sequence of resulting inorder traversal, then answer is OK :) :).
but how " Suppose we do not have a parent pointer in the nodes " maintaining?
By default, a child doesn't have pointer to parent. So, its simple Balanced BST. confirm me?
0 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
answered by Veteran (49.4k points)  
questions ask about the balanced search tree.
0 votes
Ans:D
answered by (13 points)  
answer should be (D)
Top Users Jan 2017
  1. Debashish Deka

    7172 Points

  2. Habibkhan

    4696 Points

  3. Vijay Thakur

    4308 Points

  4. sudsho

    4090 Points

  5. saurabh rai

    4024 Points

  6. Arjun

    3292 Points

  7. santhoshdevulapally

    3066 Points

  8. GateSet

    3016 Points

  9. Bikram

    3014 Points

  10. Sushant Gokhale

    2892 Points

Monthly Topper: Rs. 500 gift card

18,838 questions
23,808 answers
51,589 comments
20,148 users