Today I am going to show how to solve the Validate Binary Search Tree.
Before explaining the solution to this problem, I am going to shortly go over what a Binary Search Tree (BST) is.
Generally a tree is a data structure composed of nodes. Each tree has a root node which is the highest node and has zero or more child nodes. As stated in the problem, a Binary Search Tree is a type of tree in which each node has up to two children and adheres to the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Based on all of this, we can say that every node in BST has a minimum value and a maximum value.
Therefore, I am going to traverse the entire given tree by starting from the root node. Then, I move down from the root to validate all the subtrees by checking if all of the subtrees’ nodes are wrapped between their minimum value and maximum value. I will do this until I reach null values i.e. leaf nodes that don't have any child nodes.
For this, I created a helper method (validateBst) which takes in additional arguments, a minValue and a maxValue, and I pass down values as we traverse the tree. When I call the helper method on the left subtree of a node, I change the maximum value to be the value of our current node. When I call the function on our left subtree, I change the maximum value to be the current value of our node.
var isValidBST = function(root) {
return validateBst(root, -Infinity, Infinity)
};
function validateBst(root, minValue, maxValue) {
if(root == null) return true;
if(root.val >= maxValue || root.val <= minValue) return false;
return validateBst(root.right, root.val, maxValue) &&
validateBst(root.left, minValue, root.val)
}
Top comments (0)