# Validate Binary Search Tree in Java

Given the root of a binary tree, the task is to check whether it is a valid binary search tree (BST) or not.

A Binary Search Tree is a type of tree data structure where for every node, all the nodes in the left subtree of this node have a value lesser than the current node’s value. Each and every node in the right subtree of this node have a value greater than the current node’s value, along with the fact that both the left subtree and right subtree are Binary Search Trees.

Example 1

Input: root = [2 ,1 3]

Output: true

Example 2

Input: root = [5, 1 ,4, null, null, 3, 6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

## Approach 1: Using Brute Force Approach

A straightforward approach to check if a binary tree is BST or not is to check at every node, the maximum value in the left subtree is less than the current node’s value, and the minimum value in the right subtree is greater than the current node’s value.

Algorithm

Step 1: The isValidBST method recursively traverses the tree while maintaining a range of valid values for each node.

Step 2: At each node, it checks whether the node's value violates the BST property by comparing it with the current range.

Step 3: If the node's value is within the range, it recursively validates the left and right subtrees with updated ranges.

Step 4: The recursion continues until all nodes are checked, and the method returns true if the tree is a valid BST, otherwise false.

Filename: ValidateBSTUsingBruteForce.java

`// Class for validating a Binary Search Tree (BST) using a brute force approachpublic class ValidateBSTUsingBruteForce {    // Method to validate if a given tree is a valid BST    public boolean isValidBST(TreeNode root) {        // Call helper method with initial range as minimum and maximum integer values        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);    }    // Helper method to recursively validate a BST    private boolean isValidBST(TreeNode node, int min, int max) {        // Base case: if node is null, it's a valid BST        if (node == null)            return true;        // Check if node's value violates the BST property        if (node.val <= min || node.val >= max)            return false;        // Recursively check left and right subtrees with updated ranges        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);    }    // Main method for example usage    public static void main(String[] args) {        // Create instance of BST validator        ValidateBSTUsingBruteForce validator = new ValidateBSTUsingBruteForce();        // Create a sample BST        TreeNode root = new TreeNode(2);        root.left = new TreeNode(1);        root.right = new TreeNode(3);        // Validate the BST and print result        System.out.println(validator.isValidBST(root)); // Output: true    }}// Definition of TreeNode classclass TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;    }}`

Output

`true`

Time Complexity: The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the validation process.

Space Complexity: The space complexity of this algorithm is O(n), where n is the number of nodes in the tree. This is because the recursion stack can potentially grow to the height of the tree, which is proportional to the number of nodes in the tree.

## Approach 2: Using In-order Traversal (Iterative)

It Perform an iterative in-order traversal of the binary tree using a stack. While traversing, compare each node's value with the previous node's value. If at any point the previous node's value is greater than or equal to the current node's value, the tree is not a valid binary search tree.

Algorithm

Step 1: The algorithm uses iterative in-order traversal to visit each node of the binary tree.

Step 2: It maintains a stack to keep track of the nodes to be visited.

Step 3: At each step, it checks whether the current node's value is greater than or equal to the previous node's value.

Step 4: If this condition fails for any pair of adjacent nodes during traversal, the tree is not a valid BST.

Step 5: The algorithm returns true if all nodes satisfy the BST property.

Filename: ValidateBSTUsingIterative.java

`import java.util.Stack;public class ValidateBSTUsingIterative {    // Method to validate if a given tree is a valid BST    public boolean isValidBST(TreeNode root) {        // Stack to perform iterative in-order traversal        Stack<TreeNode> stack = new Stack<>();        // Variable to keep track of the previously visited node        TreeNode prev = null;        // Perform iterative in-order traversal        while (root != null || !stack.isEmpty()) {            while (root != null) {                stack.push(root);                root = root.left;            }            root = stack.pop();            // Check if the current node's value is greater than or equal to the previous node's value            // If yes, then the tree is not a valid BST            if (prev != null && prev.val >= root.val)                return false;            // Update prev to the current node            prev = root;            // Move to the right subtree            root = root.right;        }        // If all nodes satisfy the BST property, return true        return true;    }    public static void main(String[] args) {        // Example usage        ValidateBSTUsingIterative validator = new ValidateBSTUsingIterative();        TreeNode root = new TreeNode(2);        root.left = new TreeNode(1);        root.right = new TreeNode(3);        // Validate the BST and print result        System.out.println(validator.isValidBST(root)); // Output: true    }}// Definition of TreeNode classclass TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;    }}`

Output

`true`

Time Complexity: The time complexity of an algorithm is O(n), where n is the number of nodes in the tree. We visit each node once during the traversal.

Space Complexity: The space complexity of an algorithm is O(h), where h is the height of the tree. This is because the stack can grow up to the height of the tree, which is proportional to the maximum depth of the tree.

## Approach 3: Using Min-Max Range Approach

The Min-Max Range approach is a recursive technique used to validate whether a given binary tree is Binary Search Tree (BST) or not. In this approach, we maintain two parameters, min and max, representing the minimum and maximum values allowed for the current node.

Algorithm

Step 1: The algorithm uses recursion to traverse the binary tree.

Step 2: It maintains two parameters, min and max, which represent the minimum and maximum values allowed for the current node.

Step 3: At each node, it checks whether the node's value falls within the range defined by min and max.

Step 4: For the left subtree, the maximum value is the current node's value, and for the right subtree, the minimum value is the current node's value.

Step 5: If any node violates the BST property, the algorithm returns false.

Step 6: If all nodes satisfy the BST property, the algorithm returns true.

Filename: ValidateBSTUsingMinMax.java

`public class ValidateBSTUsingMinMax {    // Method to validate if a given tree is a valid BST    public boolean isValidBST(TreeNode root) {        // Call the helper method with initial range as null (unbounded)        return isValidBST(root, null, null);    }    // Helper method to recursively validate a BST using Min-Max range approach    private boolean isValidBST(TreeNode node, Integer min, Integer max) {        // Base case: if node is null, it's a valid BST        if (node == null)            return true;        // Check if node's value violates the BST property        if ((min != null && node.val <= min) || (max != null && node.val >= max))            return false;        // For the left subtree, the maximum value is the current node's value        // For the right subtree, the minimum value is the current node's value        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);    }    public static void main(String[] args) {        ValidateBSTUsingMinMax validator = new ValidateBSTUsingMinMax();        TreeNode root = new TreeNode(2);        root.left = new TreeNode(1);        root.right = new TreeNode(3);        // Validate the BST and print result        System.out.println(validator.isValidBST(root)); // Output: true    }}// Definition of TreeNode classclass TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;    }}`

Output

`true`

Time Complexity: The time complexity of an algorithm is O(n), where n is the number of nodes in the tree. This is because we visit each node once during the traversal.

Space Complexity: The space complexity of an algorithm is O(h), where h is the height of the tree. This is because the recursion stack can grow up to the height of the tree, which is proportional to the maximum depth of the tree.

## Approach 4: Using Morris Traversal

Morris Traversal is an efficient way to perform an in-order traversal of a binary tree without using recursion or extra space. It modifies the structure of the tree temporarily to achieve this traversal.

Algorithm

Step 2: While the current node is not null

Step 2.1: If the current node has no left child, visit the current node, and move to its right child.

Step 2.2: If the current node has a left child

Step 2.2.1: Find the rightmost node in the left subtree, i.e., the node whose right child is null.

Step 2.2.2: If the right child of this rightmost node is null, set it to the current node. This step is responsible for threading.

Step 2.2.3: If the right child of the rightmost node is already set to the current node (threaded), reset it to null, visit the current node, and move to its right child.

Step 3: Repeat this process until all nodes are visited.

Filename: ValidateBSTUsingMorrisTraversal.java

`public class ValidateBSTUsingMorrisTraversal {    public boolean isValidBST(TreeNode root) {        TreeNode prev = null;        TreeNode current = root;        while (current != null) {            if (current.left == null) {                // No left child, visit the current node                if (prev != null && prev.val >= current.val)                    return false;                prev = current;                current = current.right; // Move to the right child            } else {                // Find the rightmost node in the left subtree                TreeNode predecessor = current.left;                while (predecessor.right != null && predecessor.right != current) {                    predecessor = predecessor.right;                }                if (predecessor.right == null) {                    // Set the threaded link                    predecessor.right = current;                    current = current.left; // Move to the left child                } else {                    // Remove the threaded link                    predecessor.right = null;                    if (prev != null && prev.val >= current.val)                        return false;                    prev = current;                    current = current.right; // Move to the right child                }            }        }        return true;    }    public static void main(String[] args) {        // Example usage        ValidateBSTUsingMorrisTraversal validator = new ValidateBSTUsingMorrisTraversal();        TreeNode root = new TreeNode(2);        root.left = new TreeNode(1);        root.right = new TreeNode(3);        // Validate the BST and print result        System.out.println(validator.isValidBST(root)); // Output: true    }}// Definition of TreeNode classclass TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;    }}`

Output

`true`

Time Complexity: The time complexity of an algorithm is O(n), where n is the number of nodes in the tree. This is because of each node is visited at most twice.

Space Complexity: The space complexity of an algorithm is O(1). Morris Traversal uses constant extra space.

## Approach 5: Using Breadth-First-Search (BFS)

The breadth-first search (BFS) approach to validate whether a given binary tree is a valid Binary Search Tree (BST). This method ensures that the tree adheres to the BST property, where for every node, the values in the left subtree are less than the node's value, and the values in the right subtree are greater than the node's value.

Algorithm

Step 1: If the tree is empty (root is null), return true as an empty tree is a valid BST.

Step 2: Create a queue for level-order traversal and offer the root node to the queue.

Step 3: Perform level-order traversal using BFS.

Step 4: At each level, maintain a minimum and maximum value range (min and max) for the nodes.

Step 5: Check if the values of each node at the current level violate the BST property. If any violation is found, return false.

Step 6: Offer the left and right child nodes to the queue and update the min and max values for the next level accordingly.

Step 7: Repeat this process until all levels are processed.

Step 8: If all levels satisfy the BST property, return true.

Filename: ValidateBSTUsingBFS.java

`import java.util.LinkedList;import java.util.Queue;public class ValidateBSTUsingBFS {    // Method to validate if a given tree is a valid BST    public boolean isValidBST(TreeNode root) {        // If the tree is empty, it is a valid BST        if (root == null)            return true;        // Create a queue for level-order traversal        Queue<TreeNode> queue = new LinkedList<>();        // Offer the root node to the queue        queue.offer(root);        // Perform level-order traversal        while (!queue.isEmpty()) {            // Get the number of nodes at the current level            int size = queue.size();            // Initialize min and max values for the current level            long min = Long.MIN_VALUE;            long max = Long.MAX_VALUE;            // Process each node at the current level            for (int i = 0; i < size; i++) {                // Remove the front node from the queue                TreeNode node = queue.poll();                // Check if the node's value violates the BST property                if (node.val <= min || node.val >= max)                    return false;                // If left child exists, offer it to the queue                if (node.left != null) {                    queue.offer(node.left);                    // Update the max value for the next level                    max = node.val;                }                // If right child exists, offer it to the queue                if (node.right != null) {                    queue.offer(node.right);                    // Update the min value for the next level                    min = node.val;                }            }        }        // If all levels satisfy the BST property, return true        return true;    }    public static void main(String[] args) {        // Example usage        ValidateBSTUsingBFS validator = new ValidateBSTUsingBFS();        TreeNode root = new TreeNode(2);        root.left = new TreeNode(1);        root.right = new TreeNode(3);        // Validate the BST and print result        System.out.println(validator.isValidBST(root)); // Output: true    }}// Definition of TreeNode classclass TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;    }}`

Output

`true`

Time Complexity: The time complexity of an algorithm is O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once during the level-order traversal.

Space Complexity: The space complexity of an algorithm is O(n), where n is the number of nodes in the tree. This is because the queue can contain all nodes of the tree (if the tree is a complete binary tree), resulting in linear space usage.

## Approach 6: Using Recursion with Range

The recursive approach with range checking to validate whether a given binary tree is a valid Binary Search Tree (BST).

Algorithm

Step 1: Write a recursive function to validate each node of the binary tree.

Step 2: At each node, pass down the range of valid values that the node's value must fall within.

Step 3: For the left child, the maximum value is the parent node's value (exclusive), and the minimum value is the minimum value of the range.

Step 4: For the right child, the minimum value is the parent node's value (exclusive), and the maximum value is the maximum value of the range.

Step 5: Recurse on the left and right children, updating the range accordingly.

Step 6: If the node's value is within the range, continue validating its children recursively.

Step 7: If any violation is found (node's value is not within the range), return false; otherwise, return true.

Filename: ValidateBSTUsingRecursion.java

`public class ValidateBSTUsingRecursion {    // Method to validate if a given tree is a valid BST    public boolean isValidBST(TreeNode root) {        // Call the helper method with initial range as null (unbounded)        return isValidBST(root, null, null);    }    // Helper method for recursive validation with range checking    private boolean isValidBST(TreeNode node, Integer min, Integer max) {        // Base case: if node is null, it's a valid BST        if (node == null)            return true;        // Check if node's value violates the BST property        if ((min != null && node.val <= min) || (max != null && node.val >= max))            return false;        // For the left subtree, the maximum value is the current node's value        // For the right subtree, the minimum value is the current node's value        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);    }    public static void main(String[] args) {        ValidateBSTUsingRecursion validator = new ValidateBSTUsingRecursion();        TreeNode root = new TreeNode(2);        root.left = new TreeNode(1);        root.right = new TreeNode(3);        // Validate the BST and print result        System.out.println(validator.isValidBST(root)); // Output: true    }}// Definition of TreeNode classclass TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;    }}`

Output

`true`

Time Complexity: The time complexity of an algorithm is O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once during the recursive traversal.

Space Complexity: The space complexity of an algorithm is O(h), where h is the height of the tree. This is because the recursive calls consume stack space proportional to the height of the tree. The tree could be unbalanced, leading to a space complexity of O(n) when the tree degenerates into a linked list.