Validate Binary Search Tree

1package pkg5leetcode.blind75;2 3/*4 * Validate Binary Search Tree | LC 985 * APPROACH: Inorder must be strictly increasing.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class blind75_LC98ValidateBinarySearchTree {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15    }16 17    static Integer prev;18 19    static boolean isValidBST(TreeNode root) {20        prev = null;21        return inorder(root);22    }23 24    static boolean inorder(TreeNode node) {25        if (node == null) return true;26        if (!inorder(node.left)) return false;27        if (prev != null && node.val <= prev) return false;28        prev = node.val;29        return inorder(node.right);30    }31 32    public static void main(String[] args) {33        TreeNode root = new TreeNode(2);34        root.left = new TreeNode(1);35        root.right = new TreeNode(3);36        check(isValidBST(root), "case1");37        TreeNode bad = new TreeNode(5);38        bad.left = new TreeNode(1);39        bad.right = new TreeNode(4);40        bad.right.left = new TreeNode(3);41        bad.right.right = new TreeNode(6);42        check(!isValidBST(bad), "case2");43        System.out.println("all tests passed");44    }45 46    static void check(boolean cond, String name) {47        if (!cond) throw new AssertionError("FAILED: " + name);48        System.out.println("  PASS " + name);49    }50}