BST 2

Which of the following is a potential issue with unbalanced Binary Search Trees?

• Improved search efficiency

• Consistent O(1) insertion time

• Degraded search performance

• Automatic balancing

Which of the following traversal outputs the data in sorted order in a BST?

• Preorder

• Inorder

• Postorder

• Level order

What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree for a skewed tree ?

• O(n) for all

• O(Logn) for all

• O(Logn) for search and insert, and O(n) for delete

• O(Logn) for search, and O(n) for insert and delete

What is the purpose of the Binary Search Tree insertion algorithm?

• To add nodes randomly

• • To maintain ordering and balance

• To create a linked list

• • To ensure constant time complexity

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

• 10, 20, 15, 23, 25, 35, 42, 39, 30

• 15, 10, 25, 23, 20, 42, 35, 39, 30

• 15, 20, 10, 23, 25, 42, 35, 39, 30

• 15, 10, 23, 25, 20, 35, 42, 39, 30

In the context of BST insertion, what is a leaf node?

• Node with no children

• Node with only a left child

• • Node with only a right child

• Node with two children

Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder

• 
  

  Any one of the given three traversals is sufficient

  
  

• Either 2 or 3 is sufficient

  2 and 3

• 2 and 3

• 1 and 3

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

• 65

• 67

• 69

• 83

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

• 
  

  {10, 75, 64, 43, 60, 57, 55}

• {90, 12, 68, 34, 62, 45, 55}

• {9, 85, 47, 68, 43, 57, 55}

• {79, 14, 72, 56, 16, 53, 55}

A binary search tree is generated by inserting in order the following integers:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is

• (4, 7)

• (7, 4)

• (8, 3)

• (3, 8)