DAY 29 Binary Search Trees & AVL Tree- 18th July 2024

Which of the following properties does a Binary Search Tree (BST) satisfy?

• Each node has at most two children.

• The left subtree of a node contains only nodes with keys less than the node's key.

• The right subtree of a node contains only nodes with keys greater than the node's key.

• All of the above

What is the time complexity of searching for an element in a balanced Binary Search Tree?

• O(1)

• O(log n)

• O(n)

• O(n log n)

What is the in order traversal of the BST shown below? 4 2 1 3 6 5 7

• 4 2 1 3 6 5 7

• 1 2 3 4 5 6 7

• 7 6 5 4 3 2 1

• 4 2 3 1 6 5 7

Which operation does not necessarily preserve the BST property?

• Insertion

• Deletion

• Searching

• None of the above

What is the height of a BST with 7 nodes in its most balanced form?

• 2

• 3

• 4

• 5

Which of the following algorithms is used for searching in a BST?

• Breadth-First Search

• Depth-First Search

• Binary Search

• Linear Search

Which of the following cases can occur when deleting a node from a BST?

• The node is a leaf.

• The node has one child.

• The node has two children.

• All of the above

In a BST, the node with the minimum value is found:

• At the root

• In the leftmost node

• In the rightmost node

• In the middle node

What is the successor of a node in a BST?

• The node with the next higher key

• The node with the next lower key

• The left child

• The right child

What is the worst-case time complexity of inserting a new node in an unbalanced BST?

• O(1)

• O(log n)

• O(n)

• O(n log n)