Return the first node that breaks the BST ordering rule
A tag service keeps its tags in a binary search tree so lookups stay fast. After a buggy migration, some nodes may have ended up in the wrong place. A yes/no check is not enough for the on-call engineer: the health check must point at the first node that is out of place, so it can be moved back.
Implement findBstViolation(root, compare). It returns null if the tree is a valid binary search tree, or the first node that breaks the rule.
findBstViolation(root, compare?) // => node | null
{ value, left: nodeOrNull, right: nodeOrNull }
root is a node, or null for an empty tree (which is valid).
20 and the left subtree of 30 must be strictly between 20 and 30.compare(a, b) returns a negative number if a is less than b, a positive number if greater, and 0 if equal.compare is omitted, use < and >, which works for numbers and for strings (by code unit).Trees can be up to 3,000 levels deep.
// 8
// / \
// 3 10
// / \ \
// 1 6 14
findBstViolation(tree); // => null
// 20
// / \
// 10 30
// / \
// 5 25 25 is in the left subtree of 20, but 25 > 20
findBstViolation(tree); // => the node with value 25
// 50
// / \
// 40 30 both 45 and 30 are out of place;
// / 45 comes first in pre-order
// 45
findBstViolation(tree); // => the node with value 45
// 10
// \
// 10 duplicate
findBstViolation(tree); // => the right child (value 10)