Coding interviews
Reveal answer and reasoning
A reusable container can keep node construction private, apply one stored comparer and route all updates through invariant-preserving methods. Duplicate handling can reject, count or replace an existing key, but the choice must be consistent with search and enumeration. Balancing adds implementation complexity that should be justified by required worst-case behavior.
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. 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.
A good answer makes the preconditions as explicit as the loop: acyclic structure, valid ordering and stable links during search. It traces a successful branch and an absent value, gives O(h) rather than unconditional logarithmic cost, and avoids overflow-prone subtraction. A senior review asks where the invariant is enforced and whether writing a custom tree is necessary at all. This lesson is therefore about conditional correctness and API responsibility, not simply repeating a binary-search decision pattern on another container.
The most convincing test portfolio includes a deliberately invalid structure with an explained boundary.
What a strong answer covers
- A reusable container can keep node construction private, apply one stored comparer and route all updates through invariant-preserving methods.
- Search costs O(h) comparisons and O(1) auxiliary state.
- Checking only each node against its immediate children is insufficient to validate all descendant bounds.
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.