1.12. Searching in Binary Search Trees

Try these first

1. 1.

   What defines a binary search tree?

   Hint

   Think about how the values are arranged in a BST.

2. 2.

   Describe in-order traversal in a BST.

   Hint

   Consider the sequence of visiting nodes.

3. 3.

   What is the time complexity of searching in a balanced binary search tree?

   • O(n)
   • O(log n)
   • O(1)

   Hint

   Consider how binary search works in reducing the search space.

4. 4.

   True or False: In a binary search tree, all values in the left subtree are greater than the node's value.

   • True
   • False

   Hint

   Remember the defining property of a BST.

5. 5.

   You have a series of values to insert into a binary search tree: 10, 20, 5, 3, 7, 15. Construct the tree and perform in-order traversal.

   Hint

   Visualize inserting in sequential order while following the BST property.

6. 6.

   Given a binary search tree with values (5, 3, 8, 1, 4, 7, 9), if you were to delete the node with value 3, how would you proceed, and what would the new in-order traversal be?

   Hint

   Understand that deleting a node involves maintaining the BST properties.