Solution For Validate Binary Search Tree

Problem Statement:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example:

Input: root = [2,1,3]

Output: true

Explanation: The binary tree is:

2

/ \
1 3

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Solution:

One simple approach to solve this problem is to recursively traverse through the given binary tree. While traversing, we can keep track of the smallest and largest values seen so far for each node. We can then check if the current node’s value is within this range of the smallest and largest values seen so far. If it is not, we can immediately return false since the tree is not valid.

Algorithm:

• Initialize a variable prev to NULL.
• Define the isValidBSTUtil function to perform the following steps.
• If root equals to NULL, return true.
• Traverse the left subtree by calling the isValidBSTUtil function with root’s left child as input argument. Store its result in a variable called left.
• If prev is not NULL and root’s value is less than or equal to prev’s value, return false.
• Set prev to root.
• Traverse the right subtree by calling the isValidBSTUtil function with root’s right child as input argument. Store its result in a variable called right.
• Return true if both left and right are true, else false.
• Call the isValidBSTUtil function with root as input argument and return its result.

Pseudo Code:

bool isValidBSTUtil(Node root, Node prev)
{
if (root == NULL)
return true;

if (!isValidBSTUtil(root->left, prev))
    return false;

if (prev != NULL && root->data <= prev->data)
    return false;

prev = root;

return isValidBSTUtil(root->right, prev);

}

bool isValidBST(Node root)
{
Node prev = NULL;
return isValidBSTUtil(root, prev);
}

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we need to traverse through each node of the binary tree exactly once.

Space Complexity:

The space complexity of this algorithm is O(h), where h is the height of the binary tree. This is because we need to keep track of the previous node as we traverse through the binary tree. The maximum possible height of a binary tree is n (number of nodes), so the space complexity is O(n) in the worst case.

Conclusion:

In this problem, we have discussed how to validate a binary search tree using a recursive approach. This solution has a time complexity of O(n) and a space complexity of O(h).

Step by Step Implementation For Validate Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        // An empty tree is valid
        if (root == null) {
            return true;
        }
        
        // A tree is valid if its left subtree is valid
        // and its right subtree is valid and its value
        // is greater than all values in its left subtree
        // and less than all values in its right subtree
        return isValidBST(root.left) && isValidBST(root.right) &&
            (root.left == null || root.val > maxValue(root.left)) &&
            (root.right == null || root.val < minValue(root.right));
    }
    
    // Returns the minimum value in the tree
    private int minValue(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root.val;
    }
    
    // Returns the maximum value in the tree
    private int maxValue(TreeNode root) {
        while (root.right != null) {
            root = root.right;
        }
        return root.val;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # An empty tree is a BST
        if not root:
            return True
        
        # Check if the left subtree is a BST
        if not self.isValidBST(root.left):
            return False
        
        # Check if the current node is greater than the previous node
        if self.prev and root.val <= self.prev.val:
            return False
        
        # Set the current node as previous and move to the right subtree
        self.prev = root
        return self.isValidBST(root.right)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    // if the tree is empty, it is valid
    if (!root) return true;
    
    // check if the subtrees are valid
    if (!isValidBST(root.left) || !isValidBST(root.right)) return false;
    
    // check if the current node is greater than its left child
    // and less than its right child
    if (root.left && root.left.val >= root.val) return false;
    if (root.right && root.right.val <= root.val) return false;
    
    // if we reach this point, the tree is valid
    return true;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        // An empty tree is BST 
        if (root == NULL) 
            return true; 
  
        // if left subtree is not null  
        // then check if it is BST 
        if (root->left != NULL) 
        { 
            // if left subtree is not BST 
            if (isValidBST(root->left) == false) 
                return false; 
  
            // if left subtree is BST then 
            // check if it satisfy the condition 
            // of BST i.e. left node must be 
            // smaller than root 
            if (root->left->val >= root->val) 
                return false; 
        } 
  
        // if right subtree is not null 
        // then check if it is BST 
        if (root->right != NULL) 
        { 
            // if right subtree is not BST 
            if (isValidBST(root->right) == false) 
                return false; 
  
            // if right subtree is BST then 
            // check if it satisfy the condition 
            // of BST i.e. right node must be 
            // greater than root 
            if (root->right->val <= root->val) 
                return false; 
        } 
  
        // if both subtrees are BST 
        // then return true 
        return true; 
    } 
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        //This solution is in O(n) time and O(n) space
        
        //Edge case:
        if(root == null){
            return true;
        }
        
        //We will do an inorder traversal of the tree and store the node values in a list
        List nodeValues = new List();
        Inorder(root, nodeValues);
        
        //We will loop through the list to check if the values are in sorted order
        for(int i = 0; i < nodeValues.Count - 1; i++){
            //If the current value is greater than the next value, it is not a valid BST
            if(nodeValues[i] >= nodeValues[i + 1]){
                return false;
            }
        }
        
        //If we reach this point, it is a valid BST
        return true;
    }
    
    public void Inorder(TreeNode node, List nodeValues){
        //Edge case:
        if(node == null){
            return;
        }
        
        //We will recursively call this function on the left and right subtrees
        Inorder(node.left, nodeValues);
        nodeValues.Add(node.val);
        Inorder(node.right, nodeValues);
    }
}