= Solution
A <binary search tree> is a <binary tree> storing distinct keys from a <total order>, with every key in a node's left <subtree> smaller than that node's key and every key in its right <subtree> larger. The condition concerns entire <subtrees>, not just immediate neighbours.
For membership, start at the <root of a tree> and compare the target with the current key. \b[Return true on equality; continue into the left <subtree> for a smaller target and the right <subtree> for a larger target; return false on an empty <subtree>.] The <binary search tree> ordering ensures that a discarded <subtree> cannot contain the target. Each step descends one level, so the <algorithm> terminates and uses $O(h+1)$ <time complexity> for <height of a binary tree> $h$, under constant-time key comparison.
Back to article page
