Q: What is a BST's worst case, and how do you avoid it in practice?

State the worst case in one sentence, then MAKE IT REAL — the whole value of this question is in the practical example: "The worst case is sorted or nearly sorted input. Every new value exceeds the previous one, so it always goes down the right branch and the tree becomes a linked list: h = n, all operations O(n)." Give real examples: auto-increment IDs, timestamps, an already-sorted CSV or database export. Stress that this is not an exotic case — it is one of the most natural input shapes, which is exactly why a plain BST is rarely hand-written in production code. Then list the fixes in priority order: Use a ready-made self-balancing structure — TreeMap (a red-black tree) in Kotlin/Java, SplayTreeMap in Dart, std::map in C++. In practice this is the first answer. An AVL or Red-Black tree — rotations maintain the guarantee h = O(log n). This is what you implement if you must build it yourself. Shuffle the input — a random insertion order makes the expected height O(log n). Simple, but a probability, not a guarantee. Sorted array + binary search — if the data is static (rarely changes) this is simpler than a tree and far better for the cache. A closing line shows engineering maturity: "In practice I do not write a plain BST — I take the standard library's sorted map, or if the data is static I use a sorted array with binary search. Hand-writing a BST is an interview exercise."

Q: How do you choose between a BST and a hash map?

Frame the answer in one sentence: "The question is not about speed, it is about order." I pick a hash map when I only need lookup, insert and delete by key: O(1) average, faster than a balanced tree's O(log n). That covers the large majority of cases and is my default. I pick a tree (TreeMap / SplayTreeMap) when order is required: Iterating keys in sorted order — with a hash you must sort first, O(n log n). Range queries: all keys within [a, b] — O(log n + k) in a tree, O(n) on a hash. Floor/ceiling: "the largest key below k" — not available on a hash at all. Min/max key — O(log n) in a tree, O(n) on a hash. When a worst-case guarantee matters: a tree guarantees O(log n), while a hash is O(1) only on average. Summarise the trade-off in one line: "A hash sacrifices order for speed; a tree gives up a little speed to keep order." A practical example makes the answer memorable: "If I store user sessions by id, hash map. But if I need 'all sessions created in the last 24 hours', a sorted map keyed by timestamp — because that is a range query."

Question 1

What is a Binary Search Tree and which operations does it support, at what complexity?

Accepted Answer

Give the definition precisely, because precision is what is being tested: "A BST is a binary tree where, for every node, ALL values in the left SUBTREE are smaller and ALL values in the right SUBTREE are larger. The condition covers the whole subtree, not just the direct children." Then explain what the invariant buys: "Each comparison discards half the search space, so search, insert and delete are all O(h), where h is the tree height." Raise the crucial nuance yourself: "O(h) only means O(log n) if the tree is balanced. A plain BST does not self-balance, so in the worst case — sorted input, for example — h = n and every operation drops to O(n)." Finish with the BST's reason to exist, since interviewers usually follow up with "why not a hash map?": "A hash map is faster for single-key lookup but keeps no order. A BST gives sorted iteration, range queries and floor/ceiling operations, none of which a hash can do."

Question 2

How do you delete a node with two children from a BST?

Accepted Answer

First list the three cases so the interviewer sees your structure: "Deletion has three cases — 0 children, 1 child, 2 children. The first two are easy: I detach a leaf, and I replace a single-child node with its child." Then give the real answer: "I do not physically remove a two-child node. I find its inorder successor — the smallest value in the right subtree, i.e. one step right then all the way left. I copy the successor's value into the node, then delete the successor from the right subtree." Always add the two justifications — this is what separates a strong answer from a weak one: Why the successor? Because it is the smallest value greater than the node. Placing it there keeps everything in the left subtree smaller and everything in the right subtree larger — the invariant holds. Why does the recursion not deepen? Because the successor is the minimum of the right subtree, so it has no left child. Removing it is necessarily an easy 0- or 1-child case. Mention the symmetric alternative too: the inorder predecessor (largest in the left subtree) is equally correct. Some implementations alternate between the two to keep the tree from leaning. Complexity: O(h) — finding the successor descends at most the height of the tree once.

Question 3

How would you verify that a given binary tree is really a BST?

Accepted Answer

This question sets a deliberate trap, so name the WRONG solution first — doing that yourself makes a strong impression: "The naive approach is checking left.value < node.value < right.value at each node. That is WRONG, because the invariant covers the entire subtree. If the root is 10 with left child 5, but that 5 has a right child of 20, the local check passes — yet 20 sits in the root's left subtree and exceeds 10, so it is not a BST." Then give the two correct solutions: 1. Pass a range (min, max): each node receives the interval it is allowed to occupy. The root gets (−∞, +∞); going left tightens max to the node's value, going right tightens min. If a node falls outside its interval, it is not a BST. Time O(n), memory O(h). 2. Inorder traversal: the inorder output of a BST must be strictly increasing. Walk once, keeping only the previous value; if the current value is not greater than it, return false. This version is more compact and does not need to store the whole array. Mention the edge cases — many candidates stumble here: are duplicates allowed (is the invariant "strictly less" or "less or equal")? And if you use Int.MIN_VALUE/Int.MAX_VALUE as sentinels, the check misbehaves when those values actually appear in the tree — nullable bounds are safer.

Question 4

What is a BST's worst case, and how do you avoid it in practice?

Accepted Answer

State the worst case in one sentence, then MAKE IT REAL — the whole value of this question is in the practical example: "The worst case is sorted or nearly sorted input. Every new value exceeds the previous one, so it always goes down the right branch and the tree becomes a linked list: h = n, all operations O(n)." Give real examples: auto-increment IDs, timestamps, an already-sorted CSV or database export. Stress that this is not an exotic case — it is one of the most natural input shapes, which is exactly why a plain BST is rarely hand-written in production code. Then list the fixes in priority order: Use a ready-made self-balancing structure — TreeMap (a red-black tree) in Kotlin/Java, SplayTreeMap in Dart, std::map in C++. In practice this is the first answer. An AVL or Red-Black tree — rotations maintain the guarantee h = O(log n). This is what you implement if you must build it yourself. Shuffle the input — a random insertion order makes the expected height O(log n). Simple, but a probability, not a guarantee. Sorted array + binary search — if the data is static (rarely changes) this is simpler than a tree and far better for the cache. A closing line shows engineering maturity: "In practice I do not write a plain BST — I take the standard library's sorted map, or if the data is static I use a sorted array with binary search. Hand-writing a BST is an interview exercise."

Question 5

How do you choose between a BST and a hash map?

Accepted Answer

Frame the answer in one sentence: "The question is not about speed, it is about order." I pick a hash map when I only need lookup, insert and delete by key: O(1) average, faster than a balanced tree's O(log n). That covers the large majority of cases and is my default. I pick a tree (TreeMap / SplayTreeMap) when order is required: Iterating keys in sorted order — with a hash you must sort first, O(n log n). Range queries: all keys within [a, b] — O(log n + k) in a tree, O(n) on a hash. Floor/ceiling: "the largest key below k" — not available on a hash at all. Min/max key — O(log n) in a tree, O(n) on a hash. When a worst-case guarantee matters: a tree guarantees O(log n), while a hash is O(1) only on average. Summarise the trade-off in one line: "A hash sacrifices order for speed; a tree gives up a little speed to keep order." A practical example makes the answer memorable: "If I store user sessions by id, hash map. But if I need 'all sessions created in the last 24 hours', a sorted map keyed by timestamp — because that is a range query."

Operation	Balanced	Degenerate	Sorted array	Hash map
Search	O(log n)	O(n)	O(log n)	O(1) average
Insert	O(log n)	O(n)	O(n)	O(1) average
Delete	O(log n)	O(n)	O(n)	O(1) average
Sorted output	O(n) — inorder	O(n)	O(n) — already sorted	O(n log n) — must sort
Range query	O(log n + k)	O(n)	O(log n + k)	O(n)

Binary Search Tree

📚 Sources and documentation