1.7. Binary Search Trees

Try these first

1. 1.

   What property differentiates the left and right children of a node in a binary search tree?

   Hint

   Think about how values are organized in a BST.

2. 2.

   In a BST, if the root is 10, and there is a left child of 5, what value could the right child hold?

   Hint

   It's about the relationship between parent and child nodes.

3. 3.

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

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

   Hint

   Consider how many comparisons you might need at each level.

4. 4.

   True or False: A binary search tree can contain duplicate values.

   • True
   • False

   Hint

   Think about the fundamental definition of a BST.

5. 5.

   Construct a binary search tree from the following list of values: 20, 10, 30, 5, 15, 25, 35. Then, perform an in-order traversal.

   Hint

   Keep the BST properties in mind while inserting values and remember the traversal order.

6. 6.

   Provide an algorithm to delete a node with a specified value from the binary search tree and explain the steps involved.

   Hint

   Think about how the tree structure changes after a deletion.