Trees - Searching,Insertion,Deletion and related questions


#1

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.


#2

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)


#3

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).


#4

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


#5
  • 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)