Coding interviews
Reveal answer and reasoning
Binary-search-tree search discards one subtree only because of a stated ordering invariant. All left descendants must be smaller and all right descendants larger for this distinct-key fixture. Returning existence makes duplicate identity irrelevant, but a builder would still need a duplicate policy. The method assumes an acyclic valid BST and does not validate that property on every query. The correctness argument is conditional: if target is less than a node value, the valid BST invariant excludes it from that node's right subtree.
The algorithm therefore discards right without inspection. State this reasoning for both branches rather than describing search as merely following smaller and larger values by habit.
Search costs O(h) comparisons and O(1) auxiliary state. A balanced tree has logarithmic height, but an arbitrary BST can be a chain with linear search time. Validating the entire BST would cost O(n), so whether to validate per call or trust a builder is a separate API decision. A search bound of O(log n) needs a height or balancing guarantee.
Constructing a chain through sorted insertions can make height linear in an ordinary unbalanced BST. If the data is static and compactness matters, a sorted array with binary search may provide a simpler measured design.
What a strong answer covers
- Binary-search-tree search discards one subtree only because of a stated ordering invariant.
- The missing six fixture is valuable because it travels through existing nodes before reaching an absent child.
- Search costs O(h) comparisons and O(1) auxiliary state.
Common pitfall
Checking only each node against its immediate children is insufficient to validate all descendant bounds. A malformed right subtree can hide a smaller value and make search return false for a value that physically exists. Search correctness is conditional on structure and ordering, not on the method compiling.
Follow-up questions
- Construct a right subtree containing a value smaller than the root and demonstrate a false negative under the invalid precondition. Hint: label it a contract violation rather than changing the search to inspect every branch.
- Where would you enforce ancestor bounds if callers can construct nodes directly?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.