Questions
3 of 26
What is a Binary Search Tree (BST)? What are its properties?
Difficulty: 5/10
insertion, deletion, balancing
Binary Search Tree
A Binary Search Tree is a binary tree that maintains an ordering invariant. For a node, values in the left subtree are smaller and values in the right subtree are larger, assuming the implementation does not allow duplicates. This ordering enables efficient search, insertion, and deletion when the tree remains balanced.
javascript
- 1
Left subtree contains smaller values.
- 2
Right subtree contains larger values.
- 3
Inorder traversal produces sorted order.
- 4
Search, insertion, and deletion are O(h), where h is tree height.
- 5
For a balanced BST, these operations are typically O(log n).
- 6
For a highly skewed BST, they can degrade to O(n).
Scenario Questions
0-2 years experience
- 1We need to store usernames and support fast lookup by name. How would you use a BST for this, and what happens if the usernames arrive already sorted?
- 2If you insert the sequence 5, 3, 7, 2, 4 into an empty BST, can you walk me through the shape of the tree after each insertion?
- 3Given a BST, how would you find the smallest value that is greater than a target key?
2-5 years experience
- 1Our feature uses a BST to keep a sorted set of timestamps for event ordering, but we sometimes see O(n) search times. What could cause that and how would you debug it?
- 2We replaced a hash map with a BST to get ordered iteration. What trade‑offs are you considering, and how would you decide if the change is worthwhile?
- 3During a code review you notice the delete operation is leaving the tree unbalanced after many deletions. How would you fix the issue without rewriting the whole structure?
5-8 years experience
- 1Our service stores millions of user sessions in an in‑memory BST for range queries. Discuss scalability concerns and alternative data structures you might choose.
- 2We need to persist a BST to disk and reload it quickly after a restart. What design would you use to keep the tree balanced and minimize load time?
- 3When implementing a concurrent BST for a high‑throughput API, what synchronization strategies could you employ, and what are their performance implications?
8+ years experience
- 1Our legacy system uses a custom BST for document indexing, but the codebase is hard to maintain and doesn't handle modern workloads. How would you plan a migration to a more robust solution while minimizing downtime?
- 2Multiple services have duplicated BST logic for different domain objects. What architectural changes would you propose to unify this functionality and ensure consistency?
- 3If you were to design a library that provides generic, self‑balancing BSTs for several languages in our ecosystem, what API design, testing, and versioning considerations would you prioritize?
Follow-up Questions
- How does the tree's height affect lookup time?
- What would change if you used a self‑balancing variant?
- How would you verify correctness after a series of operations?