BST Validator

Problem Statement

Write a Java program that checks if a given tree is a valid Binary Search Tree (BST). A BST is valid if, for each node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater than the node’s value. The program should implement a method to validate the tree and test it with at least three different trees, including valid and invalid BSTs, and edge cases like a single node or empty tree. You can visualize this as inspecting a family tree where each parent’s value must be greater than all their left descendants and less than all their right descendants, ensuring the hierarchy follows strict rules.

Input:

• A binary tree represented by nodes with integer values. Output: A boolean indicating whether the tree is a valid BST, and a string representation of the tree for clarity. Constraints:
• The tree has between 0 and 10^5 nodes.
• Node values are integers in the range [-10^9, 10^9].
• Duplicate values are not allowed in the BST. Example:
• Input: Tree = [5, left: [3, left: [1], right: [4]], right: [7]]
• Output: true, "Preorder: 5 3 1 4 7"
• Explanation: All nodes satisfy the BST property.
• Input: Tree = [5, left: [3, left: [1], right: [6]], right: [7]]
• Output: false, "Preorder: 5 3 1 6 7"
• Explanation: Node 6 in the left subtree is greater than 5, violating the BST property.
• Input: Tree = []
• Output: true, "Empty"
• Explanation: An empty tree is a valid BST.

Pseudocode

CLASS Node
    SET value to integer
    SET left to Node (null by default)
    SET right to Node (null by default)
ENDCLASS

FUNCTION isValidBST(root)
    FUNCTION validate(node, min, max)
        IF node is null THEN
            RETURN true
        ENDIF
        IF node.value <= min OR node.value >= max THEN
            RETURN false
        ENDIF
        RETURN validate(node.left, min, node.value) AND validate(node.right, node.value, max)
    ENDFUNCTION
    RETURN validate(root, negative infinity, positive infinity)
ENDFUNCTION

FUNCTION toString(root)
    IF root is null THEN
        RETURN "Empty"
    ENDIF
    CREATE result as new StringBuilder
    FUNCTION preorder(node)
        IF node is null THEN
            RETURN
        ENDIF
        APPEND node.value and " " to result
        CALL preorder(node.left)
        CALL preorder(node.right)
    ENDFUNCTION
    CALL preorder(root)
    RETURN "Preorder: " + result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of trees
    FOR each testCase in testCases
        PRINT test case details
        CALL isValidBST(testCase.root)
        PRINT result and tree using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a Node class with: a. An integer value. b. left and right pointers to child nodes.
2. Define isValidBST: a. Use a helper function validate(node, min, max) to check if each node’s value is within [min, max]. b. For each node:
   • If null, return true.
   • If value is not in (min, max), return false.
   • Recursively validate left subtree with updated max = node.value.
   • Recursively validate right subtree with updated min = node.value. c. Call validate with initial min = negative infinity, max = positive infinity.
3. Define toString: a. If root is null, return "Empty". b. Perform preorder traversal, appending values to a string.
4. In main, test with at least three trees: a. A valid BST. b. An invalid BST. c. An empty tree. d. A single-node tree.

Java Implementation

public class BSTValidator {
    // Node class for the binary tree
    static class Node {
        int value;
        Node left, right;

        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    // Validates if the tree is a BST
    public boolean isValidBST(Node root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(Node node, long min, long max) {
        if (node == null) {
            return true;
        }
        if (node.value <= min || node.value >= max) {
            return false;
        }
        return validate(node.left, min, node.value) && validate(node.right, node.value, max);
    }

    // Converts tree to string (preorder traversal)
    public String toString(Node root) {
        if (root == null) {
            return "Empty";
        }
        StringBuilder result = new StringBuilder();
        preorder(root, result);
        return "Preorder: " + result.toString().trim();
    }

    private void preorder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }
        result.append(node.value).append(" ");
        preorder(node.left, result);
        preorder(node.right, result);
    }

    // Helper class for test cases
    static class TestCase {
        Node root;

        TestCase(int[] values, int[][] edges) {
            if (values.length == 0) {
                root = null;
                return;
            }
            Node[] nodes = new Node[values.length];
            for (int i = 0; i < values.length; i++) {
                nodes[i] = new Node(values[i]);
            }
            for (int[] edge : edges) {
                int parent = edge[0], child = edge[1];
                if (edge[2] == 0) {
                    nodes[parent].left = nodes[child];
                } else {
                    nodes[parent].right = nodes[child];
                }
            }
            root = nodes[0];
        }
    }

    // Main method to test BST validator
    public static void main(String[] args) {
        BSTValidator validator = new BSTValidator();

        // Test cases
        TestCase[] testCases = {
            // Valid BST: [5, left: [3, left: 1, right: 4], right: 7]
            new TestCase(
                new int[]{5, 3, 1, 4, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}}
            ),
            // Invalid BST: [5, left: [3, left: 1, right: 6], right: 7]
            new TestCase(
                new int[]{5, 3, 1, 6, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}}
            ),
            // Empty tree
            new TestCase(new int[]{}, new int[][]{}),
            // Single node
            new TestCase(new int[]{10}, new int[][]{})
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Tree: " + validator.toString(testCases[i].root));
            boolean isValid = validator.isValidBST(testCases[i].root);
            System.out.println("Is Valid BST: " + isValid + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Tree: Preorder: 5 3 1 4 7
Is Valid BST: true

Test case 2:
Tree: Preorder: 5 3 1 6 7
Is Valid BST: false

Test case 3:
Tree: Empty
Is Valid BST: true

Test case 4:
Tree: Preorder: 10
Is Valid BST: true

Explanation:

• Test case 1: Tree [5, left: [3, left: 1, right: 4], right: 7] is valid (all left subtree values < node, all right > node).
• Test case 2: Tree [5, left: [3, left: 1, right: 6], right: 7] is invalid (6 > 5 in left subtree).
• Test case 3: Empty tree is valid by definition.
• Test case 4: Single node (10) is valid (no subtrees to violate).

How It Works

• Node: Stores an integer value and pointers to left and right children.
• isValidBST:
  • Uses recursive helper validate with min and max bounds.
  • Checks if node value is within (min, max).
  • Updates bounds for left (max = node.value) and right (min = node.value) subtrees.
  • Returns true for null nodes, false if bounds violated.
• toString: Performs preorder traversal, returns space-separated values or "Empty".
• Example Trace (Test case 1):
  • Root=5: validate(5, -∞, +∞) → true.
  • Left=3: validate(3, -∞, 5) → true.
  • Left=1: validate(1, -∞, 3) → true.
  • Right=4: validate(4, 3, 5) → true.
  • Right=7: validate(7, 5, +∞) → true.
  • Result: true.
• Main Method: Tests valid BST, invalid BST, empty tree, and single node.

Complexity Analysis Table

Note:

• n is the number of nodes in the tree.
• h is the height of the tree (O(n) for skewed, O(log n) for balanced).
• Time complexity: O(n) for isValidBST and toString (visit each node once).
• Space complexity: O(h) for recursion stack in isValidBST and toString.
• Worst case: O(n) time and O(n) space for skewed trees.

✅ Tip: Use a range-based validation (min, max) to enforce the BST property recursively. Use long for bounds to handle edge cases with integer values near Integer.MIN_VALUE or MAX_VALUE.

⚠ Warning: Ensure no duplicate values in the BST, as they violate the strict inequality required. Handle empty trees and single nodes explicitly to avoid incorrect results.