Java: Validate Binary Search Tree

Thought Process

The problem requires validating whether a binary tree is a Binary Search Tree (BST) or not. A BST is valid if for every node, its value is greater than all values in its left subtree and less than all values in its right subtree. For each node, we check if its value lies within a valid range defined by minimum (mn) and maximum (mx) bounds. If the node's value is outside this range, the tree is invalid. We then recursively validate the left and right subtrees. 

/**
 * 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 validateBST(TreeNode root, long mn ,long mx){

        if(root==null)
            return true;

        // If Root satisfies the condition, then validate left & right subtree.
        if(root.val > mn && root.val < mx)
            return validateBST(root.left,mn,root.val) && validateBST(root.right,root.val,mx);
        else 
            return false;
    }
    public boolean isValidBST(TreeNode root) {
        
        return validateBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node once, making it linear in time complexity, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The algorithm uses recursion, which consumes stack space proportional to the height of the tree. In the worst case, this is O(n) for a skewed tree.

Code copied!