98. Validate Binary Search Tree

/**

 * 98. Validate Binary Search Tree

 *

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

 *

 */

See the solution at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/IsValidBST.java

Observation: Valid BST ensures that items on left of a node are less than that and those at right are greater than it. If you do an in-order traversal, you iterate over left, current and then right. After you return from left recursion you can compare if current node is greater or equal to prior value and if so, return false. This will ensure current is greater than its left systematically. You set the prev value before you recurse right. You can also implement the below code iteratively via using a stack – add current node to stack and keep adding its children on stack until no more children, pop from stack, ensure current is greater than prior, set prior to current and repeat on the right child.

Here is the code:

Integer prevVal;

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    if (!isValidBST(root.left)) {
        return false;
    }
    if (prevVal != null && root.val <= prevVal) {
        return false;
    }
    prevVal = root.val;
    return isValidBST(root.right);
}