Validate a Binary Search Tree with a Supplied Value Comparator

Determine whether a binary tree is a valid binary search tree when node values are not restricted to numeric types. A supplied comparison function can compare two node values; use it instead of numeric sentinels, arithmetic, or conversion to numbers. For the strict binary-search-tree convention, every value in a node's left subtree must compare smaller than that node's value, and every value in its right subtree must compare larger. Explain an iterative solution. ### Constraints & Assumptions - The input structure is a binary tree; no node-count or depth bound is supplied. - Values are opaque to the algorithm. Use the supplied comparison interface's less/equal/greater result; its concrete return encoding is not prescribed here. - Confirm that the comparator defines a consistent strict ordering over the supplied values. - Under the stated strict BST convention, equal values are invalid in the ordering. An empty tree is considered valid as an explicit practice convention. ### Clarifying Questions to Ask - Are duplicates permitted, and if so on which side? This formulation uses strict ordering. - What is the comparison function's actual interface and return convention? - Can the tree be deep enough that recursive traversal would exhaust the call stack? ```hint An in-order traversal exposes the global ordering of a binary tree. Checking only a node and its immediate children is insufficient. ``` ### What a Strong Answer Covers Use only the supplied comparator, check the full subtree ordering, and avoid an artificial minimum value for the first comparison. Explain the iterative traversal invariant, duplicate handling, time complexity, and stack usage. ### Follow-up Questions - How would you express ancestor bounds without numeric negative or positive infinity? - Why can immediate-child checks accept an invalid tree? - What guarantees fail if the comparator is inconsistent?