Skip to main content

Validate Binary Search Tree

Problem​

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • 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.

 

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

Solution​

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root, minNode = null, maxNode = null) {
    if (!root) {
        return true;
    } else if (minNode && root.val <= minNode.val) {
        return false;
    } else if (maxNode && root.val >= maxNode.val) {
        return false;
    } else {
        return isValidBST(root.left, minNode, root) && isValidBST(root.right, root, maxNode);
    }
};

We will implement a DFS solution. For a valid BST, we know the left subtree nodes must all be less than the root, and the right subtree nodes must all be greater than the root. Thus, we can keep track of the minNode and maxNode as we traverse down the tree to test whether all nodes in the tree fit this definition (ie. root is between the values of minNode and maxNode. Note that we update the maxNode when we go to the left child, and we update the minNode when we go to the right child.