Validating a binary search tree is a common technical interview question. There are several different methods to approach this problem but I will discuss the solution that has the best runtime, and I find most intuitive.
First off, a binary search tree is:
"a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree. The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another" (Wikipedia - Binary Search Tree).
To put it more simply, a BST is a binary tree where the left subtree of a node only contains keys less than the node's key, and the right subtree of a node only contains keys greater than the node's key. Each subtree must also be a BST (Geeks for Geeks - Binary Search Tree).
The objective of validating a binary search tree is to check that a binary tree satisfies the above requirements. My gut instinct was to think of some way to iterate through the given tree and compare keys to ultimately return true or false.
Iterating through a tree's left and right subtrees would be a complicated task. And there is a much more time efficient way to go about solving this problem - with recursion.
If we can recursively check each node as its own tree, until the function reaches the node's deepest leaf, we can solve this problem with a fairly simple approach. The challenge is defining limits for each node that satisfy the requirements for each node's left and right children, while keeping the limits of the each node's parent node.
function validateBST(root, min = Number.MIN_SAFE_INTEGER, max = Number.MAX_SAFE_INTEGER) {
if (root === null) return true;
if (root.value >= max || root.value <= min) return false;
return (
validateBST(root.left, min, root.value) &&
validateBST(root.right, root.value, max)
);
};
The above function utilizes recursion to efficiently validate a BST given its root. For the purpose of this exercise, we can access a node's value using its 'value' property, its left node using its 'left' property and its right node using its 'right' property.
When declaring the function we set three parameters: the tree's root, a minimum value (with a default value of JS's smallest integer value) and a maximum value (with a default value of JS's largest integer value). The base case is an empty tree (node value of null) which is a valid BST, and therefore returns true. The following 'if' statement compares the root's value to the minimum and maximum values passed to the function. The first recursive call will always bypass this statement. But if a child node does satisfy that 'if' statement, we know the tree is not a valid BST and the function returns false. We check the left and right child nodes with the following return statement, which calls our function, 'validateBST', with modified values for 'min' and 'max'. For the left node, 'min' is left intact and 'max' becomes the current root's value. For the right node, 'min' becomes the root's value and 'max' is left intact.
The above function has linear runtime, O(n) - 'n' being the number of nodes in the tree. I believe this solution is widely accepted as a practical method for validating a BST and should be easy to remember and conceptualize.
Top comments (1)
Nice and clean solution. I’ve built a bot which explains BST validation with the same recursive solution bot.chib.me/courses/validate-binar...
It builds intuition step by step without giving the straight answers.