State BST search assumptions explicitly

Clarify the observable contract

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.

Walk through the verified program

Searching seven compares against five, follows right to eight and then left to seven. Searching six follows the same initial path but reaches null below seven. Empty input returns false. CompareTo expresses ordering without subtracting target and node values, so extreme integers do not reverse direction through arithmetic overflow.

The missing six fixture is valuable because it travels through existing nodes before reaching an absent child. A test that searches only the root would not exercise the branch decisions. The null input additionally checks that no dereference is attempted before the loop guard has accepted a current node.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var root=new Node(5,new Node(3),new Node(8,new Node(7),new Node(9)));
Console.WriteLine("seven:" + Contains(root,7).ToString().ToLowerInvariant());
Console.WriteLine("six:" + Contains(root,6).ToString().ToLowerInvariant());
Console.WriteLine("empty:" + Contains(null,5).ToString().ToLowerInvariant());
static bool Contains(Node? node,int target) { while(node is not null) { int relation=target.CompareTo(node.Value); if(relation==0) return true; node=relation<0?node.Left:node.Right; } return false; }
sealed record Node(int Value,Node? Left=null,Node? Right=null);

Account for time, storage and allocations

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.

Review assumptions and likely defects

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.

Validation must propagate ancestor bounds through the entire subtree, not just check each parent-child pair. For example, a value in the right subtree can be smaller than the root while still being smaller than its immediate parent. This breaks search even when local comparisons look reasonable.

Practice one: discriminate edge cases

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.

Preserve the invalid-tree counterexample as a documentation test for the precondition rather than an assertion that search must succeed on every binary tree. A separate validator could reject that structure first. Mixing validation into every query changes the performance contract and should be a deliberate API choice.

Practice two: defend an extension

Design a reusable BST container that prevents invalid construction. Define duplicate insertion, balancing, comparer ownership and mutation visibility. Explain when a sorted array or a framework sorted collection would be a better interview answer than writing a tree from scratch.

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.

Evaluate correctness and interview reasoning

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.