Recall & Review
beginner
What is a Binary Search Tree (BST)?
A Binary Search Tree is a tree data structure where each node has at most two children. For every node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.
Click to reveal answer
beginner
How does the search operation work in a BST?
Start at the root. If the value equals the node's value, return it. If smaller, search the left subtree. If larger, search the right subtree. Repeat until found or reach a null node.
Click to reveal answer
intermediate
What is the time complexity of searching in a BST?
The average time complexity is O(log n) when the tree is balanced. In the worst case (skewed tree), it can be O(n).
Click to reveal answer
beginner
What happens if the search value is not in the BST?
The search will continue down the tree until it reaches a null node, meaning the value is not present. The operation returns null or indicates not found.
Click to reveal answer
intermediate
Show the TypeScript code snippet for searching a value in a BST node.
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
if (root === null || root.val === val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}Click to reveal answer
In a BST, if the search value 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 worst case time complexity of searching in a balanced BST?
✗ Incorrect
Balanced BST search takes O(log n) time because the tree height is log n.
If the search value equals the current node's value, what should the search operation do?
✗ Incorrect
When the value matches, the search returns the current node immediately.
What does the search operation return if the value is not found in the BST?
✗ Incorrect
If the value is not found, the search returns null or indicates not found.
Which traversal method is used in the BST search operation?
✗ Incorrect
BST search uses directed search by comparing values, not a full traversal.
Explain how the search operation works in a Binary Search Tree.
Think about how you decide which way to go at each node.
You got /6 concepts.
Describe the time complexity of searching in a BST and what affects it.
Consider how the shape of the tree changes search speed.
You got /4 concepts.