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. The left child contains values less than the node, and the right child contains values greater than the node.
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 the value is less, search the left subtree. If greater, 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
intermediate
Show the Go code snippet for searching a value in a BST.
func searchBST(root *TreeNode, val int) *TreeNode {
if root == nil || root.Val == val {
return root
}
if val < root.Val {
return searchBST(root.Left, val)
}
return searchBST(root.Right, val)
}
Click to reveal answer
beginner
What happens if the searched value is not in the BST?
The search will continue down the tree until it reaches a null node, then it returns nil indicating the value is not found.
Click to reveal answer
In a BST, where do you search if the target value is less than the current node's value?
✗ Incorrect
In a BST, values less than the current node are in the left subtree.
What is the best case time complexity for searching in a balanced BST?
✗ Incorrect
Balanced BST search takes O(log n) time because it halves the search space each step.
What does the search function return if the value is not found in the BST?
✗ Incorrect
If the value is not found, the search reaches a null node and returns nil.
Which of these is true about BST search?
✗ Incorrect
Search in BST follows one path from root to leaf based on comparisons.
If the BST is skewed (like a linked list), what is the search time complexity?
✗ Incorrect
In a skewed BST, search time degrades to O(n) because it behaves like a linked list.
Explain how the search operation works in a Binary Search Tree step-by-step.
Think about how you decide which way to go at each node.
You got /6 concepts.
Describe the impact of tree shape on the efficiency of BST search.
Consider how many nodes you visit in best vs worst cases.
You got /4 concepts.