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