98. Validate Binary Search Tree 🚀

Solution Developed In:

The Question

For this article, we will be covering Leetcode '98. Validate Binary Search Tree' question. This question is rated as a Medium question.

Question:

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:

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

Explaining The Question

This Question is rated Medium. Which I believe is accurate. This question is fantastic for learning about Binary Search Trees and In order Tree Traversal.

What we're being asked is to validate if the given Binary Search Tree is valid or not. Meaning it comply with the rules of a Binary Search Tree. Meaning all the lesser values are on the left and all the greater values are on the right.

Many of the solutions to this questions has you focus on the min and max values throughout the tree. This is a very common approach to solving this problem. As it checks if a min or max value is violated anywhere in the tree. Now, while this is a great approach, I think their is a simpler and better way to solve it.

The solution I am going to explain will have transferable knowledge to lots of other issues.

1. 99. Recover Binary Search Tree

Recommended Knowledge

1. Binary Tree
2. Depth First Search
3. In-order traversal
4. Binary Search Tree

What do we know?

1. We have been given a Binary Search Tree. It could be valid or not.
2. We need to validate it.
3. Their is always going to be at least 2 nodes.

How we're going to do it:

Basically, what we're going to do is to traverse the Binary Tree in In-Order. What this mean's is that the NEXT node we visit should always be greater than the previous node. If it isn't, then we know the tree is instantly invalid.

1. Set a flag to true, this flag will be used to let us know if the tree is valid or not. By default its always valid. Until we find a node that is less than the previous node.
2. We will declare a previous node pointer, as we're going to be keeping track of our previous node in the in-order traversal of the tree.
3. We will perform the in-order traversal of the tree, asking at each point in the traversal, 'Is the current node less than the previous node?' If it is, then we know the tree is invalid. So we set the flag to false.
4. If no bad nodes are found, then we know the tree is valid and the flag remains untouched.

Big O Notation:

• Time Complexity: O(n) | Where n is the number of nodes in our Binary Search Tree | As we're going to traverse all of the nodes within the tree.
• Space Complexity: O(h) | Where h is the height of the Binary Search Tree | Because we're going to store the height of the tree within the Call Stack due to the in-order traversal.

' Could this be improved? ' Yes! Morris Traversal could do this problem in O(1) space complexity. But Morris Traversal is tricky and tough to read. For the sake of simplicity, I don't use it here.

Leetcode Results:

See Submission Link:

• Runtime: 67 ms, faster than 94.56% of JavaScript online submissions for Validate Binary Search Tree
• Memory Usage: 46.8 MB, less than 22.46% of JavaScript online submissions for Validate Binary Search Tree

---

The Solution

var isValidBST = function (root) {
    // This is the flag that will be returned
    // In the event we find a node that violates the BST property, we inverted the flag.
    let is_bst_valid = true;

    // We will also be tracking the previous node.
    // This will be used to check if the current node is greater than the previous node.
    // As a valid BST, the previous node must be less than the current node.
    let prev_node = new TreeNode(-Infinity, null, null);

    // We will traverse the tree in-order.
    // As a BST traversed in-order would result in something akin to a sorted array.
    // [1,2,3,4,5,6,7,8,9]
    // In the event we see something like this:
    // [1,2,3,4,*99,6,7,8,9,10]
    // We know it's not a valid BST.
    const in_order_traverse = (node) => {

        // Empty tree. Base case.
        if (!node || !is_bst_valid) {
            return;
        }

        // Get my left nodes.
        in_order_traverse(node.left);

        // The in order section
        // Check if the current node is greater than the previous node.
        // If not, it's a invalid tree
        if (node.val <= prev_node.val) {
            is_bst_valid = false;
        }

        // Update the previous node.
        prev_node = node;
        in_order_traverse(node.right);
    };

    in_order_traverse(root);

    // Return the flag
    return is_bst_valid;
};