Binary Search Trees
A binary search tree keeps a set of values ordered for lookup, insertion, and minimum and maximum queries [Sedgewick and Wayne]. Here a HeyVL domain specifies the trees, and recursive procedures implement these operations. Do the membership, minimum, and maximum procedures return the right answers, and does insertion keep the tree ordered?
Caesar verifies partial correctness under the tree axioms, using the specifications of recursive calls.
The @uwlp annotation selects unbounded greatest fixed point semantics for the Boolean specifications written with ?(...).
Representing Trees
The Tree domain declares an empty tree nil(), a node constructor node, and selectors for each node's integer value and children:
domain Tree {
// Constructors for the empty tree and a node with two children.
func nil(): Tree
func node(left: Tree, value: Int, right: Tree): Tree
// Selectors recover the corresponding argument of a constructed node.
func left_child(tree: Tree): Tree
axiom left_child_node forall left: Tree, value: Int, right: Tree.
left_child(node(left, value, right)) == left
func root_value(tree: Tree): Int
axiom root_value_node forall left: Tree, value: Int, right: Tree.
root_value(node(left, value, right)) == value
func right_child(tree: Tree): Tree
axiom right_child_node forall left: Tree, value: Int, right: Tree.
right_child(node(left, value, right)) == right
// A tree is empty precisely when it equals nil().
func is_nil(tree: Tree): Bool
axiom is_nil_def forall tree: Tree.
is_nil(tree) == (tree == nil())
// A constructed node is never empty.
axiom node_not_nil forall left: Tree, value: Int, right: Tree.
node(left, value, right) != nil()
These axioms do not say that every tree is built from finitely many nodes.
The proofs therefore do not establish that recursion terminates for every value of type Tree.
Checking Membership
The recursive function contains specifies whether a value occurs at the root or in either subtree:
// Membership holds at the root or in either subtree.
func contains(tree: Tree, value: Int): Bool =
ite(
is_nil(tree),
false,
(value == root_value(tree)) ||
contains(left_child(tree), value) ||
contains(right_child(tree), value)
)
The procedure contains_value checks the root, then searches the subtrees until it finds the value.
It needs no ordering assumption on its input:
Verified@uwlp
proc contains_value(tree: Tree, value: Int) -> (present: Bool)
post ?(present == contains(tree, value))
{
if is_nil(tree) {
present = false
} else {
var root: Int = root_value(tree)
if value == root {
present = true
} else {
var in_left: Bool = contains_value(left_child(tree), value)
if in_left {
present = true
} else {
present = contains_value(right_child(tree), value)
}
}
}
}
Each recursive call gives the membership result for its subtree. Combining those results with the comparison at the root proves the caller's postcondition.
Finding the Minimum and Maximum
Both queries require a nonempty tree satisfying is_bst:
// Both subtrees are ordered, with left values below and right values above the root.
func is_bst(tree: Tree): Bool =
ite(
is_nil(tree),
true,
is_bst(left_child(tree)) &&
is_bst(right_child(tree)) &&
(forall value: Int. contains(left_child(tree), value) ==> (value < root_value(tree))) &&
(forall value: Int. contains(right_child(tree), value) ==> (root_value(tree) < value))
)
The predicate requires both subtrees to be ordered, with all left values below the root and all right values above it.
Minimum
The function min_value follows left children:
func min_value(tree: Tree): Int =
ite(is_nil(left_child(tree)), root_value(tree), min_value(left_child(tree)))
The procedure get_min finds this minimum:
Verified@uwlp
proc get_min(tree: Tree) -> (result: Int)
pre ?(is_bst(tree) && !is_nil(tree))
post ?(
(result == min_value(tree)) &&
contains(tree, result) &&
(forall value: Int.
(contains(tree, value) && (value != result)) ==> (result < value))
)
{
var left: Tree = left_child(tree)
var root: Int = root_value(tree)
if is_nil(left) {
result = root
} else {
result = get_min(left)
}
}
If the left child is empty, the root is the minimum.
Otherwise, the recursive call gives the minimum of the nonempty left child.
By is_bst, that value is also smaller than the root and every member of the right subtree.
Maximum
The function max_value follows right children:
func max_value(tree: Tree): Int =
ite(is_nil(right_child(tree)), root_value(tree), max_value(right_child(tree)))
The procedure get_max verifies that this value is the largest member:
Verified@uwlp
proc get_max(tree: Tree) -> (result: Int)
pre ?(is_bst(tree) && !is_nil(tree))
post ?(
(result == max_value(tree)) &&
contains(tree, result) &&
(forall value: Int.
(contains(tree, value) && (value != result)) ==> (value < result))
)
{
var right: Tree = right_child(tree)
var root: Int = root_value(tree)
if is_nil(right) {
result = root
} else {
result = get_max(right)
}
}
The proof mirrors the minimum query, using the right child's specification and the ordering of the left subtree.
Inserting a Value
The procedure insert_value adds the supplied value to a tree satisfying is_bst.
Its two post clauses require the result to remain ordered and describe exactly which values it contains:
Verified@uwlp
proc insert_value(tree: Tree, value: Int) -> (result: Tree)
pre ?(is_bst(tree))
post ?(is_bst(result))
post ?(forall witness: Int.
contains(result, witness) == (contains(tree, witness) || (witness == value)))
{
if is_nil(tree) {
result = node(nil(), value, nil())
} else {
var left: Tree = left_child(tree)
var root: Int = root_value(tree)
var right: Tree = right_child(tree)
if value < root {
var new_left: Tree = insert_value(left, value)
result = node(new_left, root, right)
} else {
if root < value {
var new_right: Tree = insert_value(right, value)
result = node(left, root, new_right)
} else {
result = tree
}
}
}
}
The recursive call tells us which values are in the modified child and that they are ordered.
The comparison with the root ensures that rebuilding the parent preserves is_bst.
The result contains exactly the old members together with the inserted value.
The complete source also includes insert_example, which inserts 4, 2, 8, and 6, then uses these specifications to check membership, minimum 2, and maximum 8.
See Also
- Left Padding verifies that padding preserves the original list as a suffix.
- Symbolic list operations uses constructors, selectors, and recursive specifications for linked lists.
References
-
Sedgewick and Wayne. Algorithms.
Introduces binary search trees as an implementation of ordered symbol tables.
(Section 3.2, “Binary Search Trees”) -
Bjørner et al. (2019). Programming Z3.
Introduces native SMT datatypes using a binary tree and explains their constructor and finiteness properties.
(Section 3.5, “Algebraic Datatypes”) -
Domains explains how to declare types, functions, and axioms in HeyVL.
-
Boolean procedure specifications explains the
pre ?(...)andpost ?(...)notation used by the tree operations.