Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a 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.

var isValidBST = function(root) {
    return checkNode(root,null,null);
};

//helper function for recursion
function checkNode(node, lower, upper) {
    //all nodes to left of node should be less than this node value
    //all nodes to right of node should be more than this node value
    
    if (!node) {
        return true; //empty so at end of path
    }
    console.log("Checking ", node.val, lower, upper);
    //check both sides
    if (lower!=null && node.val<=lower) { //this node below the limit
        return false;
    }
    if (upper!=null && node.val>=upper) { //this node above the limit
        return false;
    }
    if (!checkNode(node.left,lower,node.val)) {
        return false;
    }
    if (!checkNode(node.right,node.val,upper)) {
        return false;
    }
    return true;
}

Approaches
This is a fairly common problem and fit for recursion. Notice the third condition of what a binary search tree is; the first thing I think of when I see that is to recursively check from top-down or bottom-up that all conditions are met. Return false if it fails at any point, and return true if always true for every point.

Code Breakdown
As usual, let’s break down the code part by part.

var isValidBST = function(root) {
    return checkNode(root,null,null);
};

This simply calls a helper function, checkNode. Often times with recursion problems you want to make a helper function. It may be because you want to set up some logic before/after the recursion algorithm, or simply because the function definition you’re given for the challenge could use some extra parameters. In this case it’s the latter. If we weren’t given a function definition, we could modify it so that the function has two additional default parameters that’ll be set to null if nothing is passed in.

Now let’s look at the helper function.

    if (!node) {
        return true; //empty so at end of path
    }

This is the terminal condition of the recursion. When we get to the end, a branch without valid children will be null, and that’s what’s passed to the helper function. Recall we fail if it fails at any point, so since a null child doesn’t imply it’s not a BST, we return true so it recurses up properly.

    //check both sides
    if (lower!=null && node.val<=lower) { //this node below the limit
        return false;
    }
    if (upper!=null && node.val>=upper) { //this node above the limit
        return false;
    }

Javascript Note: The first part of the condition is to make sure that limitation exists before we check it. In Javascript, if a multi-condition statement fails at any condition where it needs to all be true for it to execute, it’ll stop checking the other conditions.

Here we check both children of the binary tree. Recall our initial conditions on the left and right paths.

all nodes to left of node should be less than this node value
all nodes to right of node should be more than this node value

This checks if the current node’s value is:

greater than the lowest number we’ve seen so far
less than the highest number we’ve seen so far

Put another way, it is NOT a BST if at any point the current node’s value is:

less than or equal to the lowest we’ve seen so far (recall no duplicates)
greater than or equal to the highest we’ve seen so far

    if (!checkNode(node.left,lower,node.val)) {
        return false;
    }
    if (!checkNode(node.right,node.val,upper)) {
        return false;
    }

This is where we do the recursion. We check the left child’s tree and the right child’s tree, and if either path isn’t a BST, it fails and we return false.
For the left tree, we pass along the lowest value we’ve seen so far as the lower bound, and the current node’s value as the upper bound. Recall the initial conditions where everything to the left of the tree is lower than the current node’s value.
For the right tree, we do something similar but we pass in the current node value as as the new lower bound, and we pass along the prior upper bound as well. Recall for the right path, all values must be greater than the current node’s value.

    return true;

If it hasn’t failed the checks for the current node, and neither child’s path fails, then we return true. This is important not just for the root node but also for the recursion itself. Recall above when we check the child nodes, we check if the helper function returns true to indicate that the child path is a BST. This return true that the node represents the root of a BST is what makes that possible.