A binary search tree is a binary tree that keeps its values ordered for fast lookup. Its invariant is that for any node, all values in its left subtree are smaller and all values in its right subtree are larger.
The rule covers whole subtrees, not just direct children, so a value deep in the left subtree must stay below the ancestor it descends from.
The invariant makes search cheap. At each node you compare, then discard a whole subtree and follow the other side. Duplicates need a chosen policy, such as always going right or storing a count. Keep the invariant true on every insert and delete, and lookups stay logarithmic on a balanced tree. Break it anywhere and searches can miss values that are present.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
How would you handle duplicate keys?Pick one policy, like a count per node or equal keys always going right, and make insert, search and delete all follow it.
What you can say
A binary search tree is a binary tree that keeps its values in order, so you can find a value without looking at every node.
The invariant is that for any node, everything in its left subtree is smaller and everything in its right subtree is larger.
That rule covers whole subtrees, not just direct children, so a node deep in the left subtree still has to be smaller than the ancestor above it.
That's what makes search cheap. At each node you compare once, skip one whole subtree and follow the other side.
Duplicates need a policy you choose up front, like always sending equal keys right or keeping a count on the node.
The catch is that lookups are only logarithmic on a balanced tree, and if an insert or delete breaks the invariant, searches can miss values that are actually there.
Weak answers to avoid
Only compares a node with its childrenLeft child < node < right child is a weaker rule. Say the invariant covers whole subtrees, or a deep node can end up on the wrong side of an ancestor.
Claims BST lookups are always O(log n)That holds only on a balanced tree. Sorted inserts build a chain of height n, so search is O(n). Say the cost is O(height).
Ignores duplicate keysLeaving equal keys undefined lets insert and search disagree. Name a policy, such as always going right or keeping a count.
Mixes up a BST with a heapA heap only orders each parent against its children, so search can't skip a subtree. A BST orders left against right, and that lets search discard one.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
