Trees - Searching,Insertion,Deletion and related questions


This is about questions on tree data structure.Discussion on past gate questions,how to approach questions involving trees and answering questions based on trees.


The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is

A) \Theta(n log n)

B) \Theta (n2^n)

C) \Theta (n)

D) \Theta (log n)


Time taken to search an element is Θ(h) where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be Θ(Log(n*2^n)) which is Θ(Log(n) + Log(2^n)) Which is Θ(Log(n) + n) which can be written as Θ(n).


the answer is A) Theta(n log n).

  • Binary search complexity for worst case is Theta(log n).so equation is Theta(n2^n)
    Evaluating this equation:-
    –Theta(log n + log 2^n) Here is log2^n the power to which the number 2 must be raised to obtain the value n.
    so 2^n---->n
    –Theta(log n +log n)
    –Theta(n ) ----By Big O formula

  • Answer is Theta(n)