1.10. Binary Search Tree Properties

Try these first

1. 1.

   What is a binary search tree?

   Hint

   Think about the structure and order of elements.

2. 2.

   What type of traversal gives you sorted order of elements in BST?

   Hint

   Recall the order of visiting nodes.

3. 3.

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

   • O(n)
   • O(log n)
   • O(n^2)

   Hint

   Remember the effects of balance on performance.

4. 4.

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

   • True
   • False

   Hint

   Consider the definition of a binary search tree.

5. 5.

   You have to implement a BST and ensure it remains balanced after a series of insertions and deletions. What steps would you take?

   Hint

   Consider the properties of each type of self-balancing tree.

6. 6.

   Create a function to perform an in-order traversal on a given BST and return the sorted list of values. Write the pseudocode.

   Hint

   Pseudocode should reflect the traversal pattern: left, root, right.