import {isSorted} from '@aureooms/js-sort';
const hasBinarySearchProperty = (compare, tree) => {
const array = [...tree];
return isSorted(compare, array, 0, array.length);
};
const hasBinarySearchPropertyAndDoesNotContainDuplicates = (compare, tree) => {
const strictCompare = (a,b) => compare(a,b) <= 0 ? -1 : 1;
// const strictCompare = (a,b) => compare(a,b) < 0 ? -1 : 1; // ugly because the choice of `<=` vs `<` depends on the implementation of `hasBinarySearchProperty` and actually does not work in the general case
return hasBinarySearchProperty(strictCompare, tree);
const hasBinarySearchProperty = (compare, node, left = undefined, right = undefined) => {
if (node === null) return true;
if (left !== undefined && compare(node.key, left) < 0) return false;
if (right !== undefined && compare(node.key, right) > 0) return false;
// if (right !== undefined && compare(right, node.key) < 0) return false; // if using the `strictCompare` trick
return hasBinarySearchProperty(compare, node.left, left, node.key) && hasBinarySearchProperty(compare, node.right, node.key, right);
};
const hasBinarySearchPropertyAndDoesNotContainDuplicates = (compare, node, left = undefined, right = undefined) => {
if (node === null) return true;
if (left !== undefined && compare(node.key, left) <= 0) return false;
if (right !== undefined && compare(node.key, right) >= 0) return false;
return hasBinarySearchProperty(compare, node.left, left, node.key) && hasBinarySearchProperty(compare, node.right, node.key, right);
};
See https://en.wikipedia.org/wiki/Binary_search_tree#Verification