ProblemsTemplatesA search tree the compiler can verify
ExpertTemplates

A search tree the compiler can verify

Context

The classic interview trap applies even at compile time: checking only child against parent is NOT enough — a grandchild can violate the order against the grandparent. The correct check carries an allowed (lo, hi) range down the recursion. Here the recursion runs on types and the ranges are template parameters.

Task

A binary tree is encoded in types: TreeNode<5, TreeNode<3>, TreeNode<8>>. Implement is_bst_v<Tree> — a compile-time check that the tree is a valid binary search tree: everything in the left subtree is smaller, everything in the right is larger, recursively.

Constraints

  • is_bst_v<TreeNode<V>> (a leaf) is true
  • Left subtree values are strictly below the node, right strictly above — RECURSIVELY (the grandparent rule)
  • Duplicates make it not a BST
  • Pure compile time; TreeNode is given and must not change

Before you code

  • Why does comparing only with the direct parent miss invalid trees?
  • What do the lo/hi bounds represent at every node?
  • How does the void base case terminate the recursion?

Tests

  • #1Valid trees pass
  • #2The grandparent rule catches deep violations
  • #3Duplicates are not a BST

Hints

Hint 1

Carry two bounds through the recursion: the left child must fit in (lo, V), the right in (V, hi).

Hint 2

Make the bounds long long and start wider than any int — then the root accepts every int value.

Editorcompile-time-bst.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.

A search tree the compiler can verify — CppForge