Which of the following statements is wrong about trees?

Which of the following is correct?

A. Running time cost O(n) B. Running time cost O(1) C. Running time cost O(logn)

Given a traversal result abcdfge and following statements -

1. Above traversal is PreOrder Traversal
2. Above traversal is PostOrder Traversal
3. Above traversal is InOrder Traversal
4. For the given tree, a is the root of the tree
5. For the given tree, e is the root of the tree Which of the above statements is/are correct?

   Given an algorithm to traverse a tree Traverse(Node v){ visit(v); for each child w of v Traverse(w); }

What would come in place of y and z respectively in the above algorithm?

An iterative algorithm to search for key k in a tree T is given below-
 search(T,k)
{
x = root(T);
while(x!=null or x!= k)
{
if(x < k) x= right[x];
else y
}
return z; 
}

The above algorithm ____________.

Following is an algorithm to return a key in a BST(Binary Search Tree).
Returnkey(Tree T)
{
x= root[T];
while(right[x] != null)
{
x = right[x];
}
return x;
}

After insertion of n keys, worst case running time of the algorithm would be _______________

An iterative algorithm to search for key k in a tree T is given below-
Assume that the tree has n nodes and height h.
search(T,k)
{
x = root(t);
while(x!=null or x!= k)
{
if(x > k) x= left[x];
else x = right[x];
}
return x;
}

This algorithm _______.

Given below is an algorithm:
if(right[x] != null)
{
x = right[x];
Treemin(x);
}
else
{
y = parent[x];
while(y !=null && x = right[y])
{
 x=y; y=parent[y];
}
return y;
}

Given numbers 1, 2, 3, 4, 5, 6…. N. Inorder to insert a random permutation of the numbers in binary search tree, what is the average running time?

What technique is used to get a good running time for an algorithm such as quick sort, which has bad worst case running time but good average case?

Which of the following is not correct about quicksort algorithm?

Which of the following statements is incorrect about a complete binary tree with n nodes and height h?

What is the running time of the algorithm?

An iterative algorithm to search for key k in a tree T is given below. Assume that the tree has n nodes and height h.
search(T,k)
{
x = root(t);
while(x!=null or x!= k)
{
if(x < k) x= right[x];
else x = left[x];
}
return x;
}

What would come in place of two in the above algorithm?

Here is an algorithm to insert a key k in a binary search tree T.
insert(T,k)
{
int flag = 0;
node x = root[T]; i
if(x == null)
{
root = new node(k);
}
while(x != null)
{
if(x > k)
{
y = x;
x = left[x];
flag = 1;
}
else
{
y = x;
x = right[x];
flag = 2;
}
}
if(flag ==1)
{
k = ?;
}
else
{
k = ?;
}
}

Given a sequence of numbers 8, 4, 9, 3, 2, 0, 11, 10 to be inserted in the tree. Which key will be visited last in the inorder traversal of the inserted keys?

Here is an algorithm to insert a key k in a binary search tree T.
insert(T,k)
{
int flag = 0;
node x = root[T];
if(x == null)
{
root = new node(k);
}
while(x != null)
{
if(x > k)
{
Y = x;
X = left[x];
flag = 1;
}
else
{
Y = x;
X = right[x];
flag = 2;
}
}
if(flag ==1)
{
K = left[y];
}
else
{
K = right[y];
}
}

What should come in place of ? in the above algorithm?

An algorithm to delete the node/key k from a tree T is given below:
delete(T, k)
{
if(left[k] == null && right[k] == null)
{
K = null;
}
else if(left[k] != null && right[k] == null)
{
if(k == left[parent[k]]) left[parent[k]] == left[k];
else right[parent[k]] = left[k];
 }
else if(left[k] == null && right[k] != null)
{
if(k == left[parent[k]]) left[parent[k]] == right[k];
else right[parent[k]] = right[k];
 }
else Y = ?;
X = y;
Right[x] = left[y];
 }
}