41.2.7 Validating binary trees

The following syntactic bindings are exported by the library (vicare containers binary-search-trees). The bindings whose name is prefixed with $ are unsafe operations: they do not validate their arguments before accessing them.

Function: binary-tree-valid? root key<

Function: $binary-tree-valid? root key<

Traverse a binary search tree from root verifying that: all the left subtrees have sort key less than that of their parents; all the right subtrees have sort key greater than, or equal to, that of their parents.

The argument root must be #f, to represent an empty tree, or an instance of <binary-node> representing the root of the tree.

The argument key< must be a procedure taking 2 arguments being instances of <binary-node>: it must return true if the first argument has sort key less than the sort key of the second argument; otherwise it must return #f.