26.1.3. Binary Search Trees (BSTs)

Try these first

1. 1.

   Define a Binary Search Tree.

   Hint

   Focus on the structure and sorting properties.

2. 2.

   What is the average time complexity for searching in a balanced BST?

   Hint

   Consider how a BST is navigated.

3. 3.

   What is the primary property of a Binary Search Tree?

   • Every node can have multiple children
   • Left child < Parent < Right child
   • All nodes are random

   Hint

   Recall how the child nodes relate to their parent.

4. 4.

   Is it true that inserting into an unbalanced BST can lead to O(n) time complexity?

   • True
   • False

   Hint

   Think about what an unbalanced tree looks like.

5. 5.

   Given a sorted array of numbers, create a balanced BST. Explain the process.

   Hint

   Consider how you would split data to keep it balanced.

6. 6.

   Consider a BST that is highly unbalanced. Suggest a plan to balance it and justify your choice.

   Hint

   Recall how balance factors play a role in keeping trees managed.