Coding interviews
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);
Reveal answer and reasoning
The output lines, in order, are “seven:true”; “six:false”; “empty:false”. 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.
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.
What a strong answer covers
- Exact output: seven:true | six:false | empty:false
- Searching seven compares against five, follows right to eight and then left to seven.
- 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.