Recall & Review
beginner
What is a Binary Search Tree (BST)?
A Binary Search Tree is a special type of binary tree where each node has at most two children. For every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property helps in efficient searching.
Click to reveal answer
beginner
How does searching work in a BST?
To search for a value, start at the root. If the value equals the root, you found it. If the value is smaller, search the left subtree. If larger, search the right subtree. Repeat until you find the value or reach a leaf node.
Click to reveal answer
intermediate
Why is searching in a BST efficient compared to a regular binary tree?
Because of the BST property, you can ignore half of the tree at each step. This reduces the search time to about log₂(n) steps on average, where n is the number of nodes, making it much faster than searching every node.
Click to reveal answer
beginner
What happens if the value is not found in the BST during search?
If the search reaches a leaf node without finding the value, it means the value is not in the tree. The search ends with a negative result.
Click to reveal answer
intermediate
What is the worst-case time complexity of searching in a BST?
In the worst case, the BST can become like a linked list (all nodes have only one child). Then, searching takes O(n) time, where n is the number of nodes.
Click to reveal answer
In a BST, if the value you are searching for is less than the current node's value, where do you search next?
✗ Incorrect
In a BST, smaller values are always in the left subtree.
What is the average time complexity of searching in a balanced BST?
✗ Incorrect
Balanced BSTs allow searching in logarithmic time, O(log n).
If a BST has 15 nodes, approximately how many steps does it take to find a value on average?
✗ Incorrect
Log base 2 of 15 is about 4, so about 4 steps on average.
What does it mean if the search in a BST reaches a leaf node without finding the value?
✗ Incorrect
Reaching a leaf without finding the value means it is not present.
What is the worst-case shape of a BST that causes slow searching?
✗ Incorrect
A BST shaped like a linked list causes O(n) search time.
Explain how searching for a value works in a Binary Search Tree.
Think about how the BST property guides the search direction.
You got /5 concepts.
Describe why searching in a BST is generally faster than searching in a regular binary tree.
Focus on how the BST structure helps reduce search steps.
You got /4 concepts.