Validate Binary Search Tree - Java Solution

1. Introduction

This blog post discusses the problem of validating a binary search tree (BST). In computer science, a BST is a fundamental data structure that facilitates fast lookup, addition, and removal operations. A valid BST is defined by specific properties regarding the arrangement of nodes, which we will explore and validate in this problem.

Problem

Given the root of a binary tree, the task is to determine if it is a valid binary search tree (BST). A BST is valid if and only if every node follows two key rules: all nodes in the left subtree have keys less than the node's key, and all nodes in the right subtree have keys greater than the node's key. Furthermore, each subtree itself must also be a valid BST.

2. Solution Steps

1. Use a recursive approach to check each node in the tree.

2. At each node, compare its value with the permissible range of values it can hold, given the structure of a BST.

3. Pass down the updated permissible range to each subtree.

4. Return true if all nodes satisfy the BST properties, false otherwise.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class ValidateBinarySearchTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(isValidBST(root)); // Test the function
    }

    // Function to validate a binary search tree
    public static boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // Helper function to validate the BST recursively
    private static boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;

        if (node.val <= min || node.val >= max) return false;

        // Check the subtrees with updated ranges
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}

Output:

true

Explanation:

1. isValidBST: This function initiates the BST validation process, calling a recursive helper function validate.

2. validate: A recursive function that checks if each node adheres to the BST properties. It receives three arguments: the current node, and the minimum and maximum values that the node's value should lie between.

3. The function checks if the current node's value falls within the permissible range. If not, it returns false.

4. The function then recursively checks the left subtree (where all values must be less than the current node's value) and the right subtree (where all values must be greater).

5. The base case for the recursion is when a null node is reached, indicating a valid path in the BST.

6. If all nodes in the tree satisfy these constraints, the function returns true, confirming that the tree is a valid BST.