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]
![Validate Binary Search Tree in Java](https://static.tutorialandexample.com/java/validate-binary-search-tree-in-java1.png)
Output: true
Example 2
Input: root = [5, 1 ,4, null, null, 3, 6]
![Validate Binary Search Tree in Java](https://static.tutorialandexample.com/java/validate-binary-search-tree-in-java2.png)
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 approach public 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 class class 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 Stackstack = 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 class class 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 class class 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 1: Start with the current node as the root.
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 class class 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 Queuequeue = 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 class class 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 class class 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.