Validate Binary Search Tree

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, nullptr, nullptr);
    }
    
    bool validate(TreeNode* node, TreeNode* minNode, TreeNode* maxNode) {
        if (node == nullptr) {
            return true;
        }
        
        if ((minNode && node->val <= minNode->val) || (maxNode && node->val >= maxNode->val)) {
            return false;
        }
        
        return validate(node->left, minNode, node) && validate(node->right, node, maxNode);
    }
};

                                            
/**
 * 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) {
        return isValid(root, null, null);
    }
    
    private boolean isValid(TreeNode node, Integer min, Integer max) {
        if (node == null)
            return true;
        
        if ((min != null && node.val <= min) || (max != null && node.val >= max))
            return false;
        
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
        
class Solution(object):
    def isValidBST(self, root):
        def helper(node, lower=float('-inf'), upper=float('inf')):
            if not node:
                return True
            val = node.val
            if val <= lower or val >= upper:
                return False
            if not helper(node.right, val, upper):
                return False
            if not helper(node.left, lower, val):
                return False
            return True
        
        return helper(root)

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return IsValidBST(root, null, null);
    }
    
    private bool IsValidBST(TreeNode node, TreeNode min, TreeNode max) {
        if (node == null) return true;
        
        if ((min != null && node.val <= min.val) || (max != null && node.val >= max.val))
            return false;
        
        return IsValidBST(node.left, min, node) && IsValidBST(node.right, node, max);
    }
}

                                            
/**
 * 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)
 * }
 */
var isValidBST = function(root, min = -Infinity, max = Infinity) {
    if (!root) {
        return true;
    }
    
    if (root.val <= min || root.val >= max) {
        return false;
    }
    
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode, right?: TreeNode) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isValidBST(root: TreeNode | null, min: number = -Infinity, max: number = Infinity): boolean {
    if (!root) {
        return true;
    }
    
    if (root.val <= min || root.val >= max) {
        return false;
    }
    
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) {
 *         $this->val = $value;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $min
     * @param Integer $max
     * @return Boolean
     */
    function isValidBST($root, $min = null, $max = null) {
        if ($root === null) {
            return true;
        }
        
        if (($min !== null && $root->val <= $min) || ($max !== null && $root->val >= $max)) {
            return false;
        }
        
        return $this->isValidBST($root->left, $min, $root->val) && $this->isValidBST($root->right, $root->val, $max);
    }
}

                                            
class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        return validate(root, null, null)
    }
    
    fun validate(node: TreeNode?, min: Int?, max: Int?): Boolean {
        if (node == null) {
            return true
        }
        
        if ((min != null && node.`val` <= min) || (max != null && node.`val` >= max)) {
            return false
        }
        
        return validate(node.left, min, node.`val`) && validate(node.right, node.`val`, max)
    }
}

                                            
// Definition for a binary tree node.
// type TreeNode struct {
//     Val int
//     Left *TreeNode
//     Right *TreeNode
// }

func isValidBST(root *TreeNode) bool {
    var prev *TreeNode
    return inorder(root, &prev)
}

func inorder(node *TreeNode, prev **TreeNode) bool {
    if node == nil {
        return true
    }
    
    if !inorder(node.Left, prev) {
        return false
    }
    
    if *prev != nil && node.Val <= (*prev).Val {
        return false
    }
    
    *prev = node
    return inorder(node.Right, prev)
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def is_valid_bst(root)
    def valid_bst_helper(node, min, max)
        return true if node.nil?
        
        if (min != nil && node.val <= min) || (max != nil && node.val >= max)
            return false
        end
        
        return valid_bst_helper(node.left, min, node.val) && valid_bst_helper(node.right, node.val, max)
    end
    
    valid_bst_helper(root, nil, nil)
end

                                            
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn is_valid(node: &Option<Rc<RefCell<TreeNode>>>, min: Option<i64>, max: Option<i64>) -> bool {
            match node {
                None => true,
                Some(n) => {
                    let val = n.borrow().val as i64;
                    if let Some(min_val) = min {
                        if val <= min_val {
                            return false;
                        }
                    }
                    if let Some(max_val) = max {
                        if val >= max_val {
                            return false;
                        }
                    }
                    is_valid(&n.borrow().left, min, Some(val)) && is_valid(&n.borrow().right, Some(val), max)
                }
            }
        }
        is_valid(&root, None, None)
    }
}

To solve this coding challenge, we need to determine if a given binary tree is a valid Binary Search Tree (BST). A binary tree is a BST if, for each node in the tree, all the values in the left subtree are less than the node's value, and all the values in the right subtree are greater than the node's value. Additionally, both left and right subtrees must themselves be BSTs.

Explanation

To validate if a binary tree is a BST, we can use a recursive approach. We will use a helper function that checks whether the tree rooted at a given node is a BST within a particular range of values. Initially, the range is between negative infinity and positive infinity. As we traverse the tree:

We check if the node's value lies within the current valid range.
For the left subtree of the node, we update the upper limit to the node's value, and for the right subtree, we update the lower limit to the node's value.
If any node violates the BST property (i.e., lies outside the valid range), the function will return False immediately.
If we reach a leaf node (i.e., a node with no children), we return True, indicating that this part of the tree is a valid BST.

Below is a very detailed step-by-step pseudocode on how to implement this:

Step-by-Step Explanation

Define the main function
isValidBST

that accepts the root of the tree.
Define the helper function
helper

, which will be called recursively.
The
helper

function checks if a given node's value is within a specified range (
lower

,
upper

).
If the node is None (i.e., it's a leaf's child), return True because leaf nodes don't violate BST properties.
If the node's value is less than or equal to the lower bound or greater than or equal to the upper bound, return False.
Recursively call the helper function for the right subtree with updated lower bound and for the left subtree with an updated upper bound.
If all subtrees are valid, return True.

Detailed Steps in Pseudocode

                                            
# Main function to validate if the binary tree is a BST
function isValidBST(root):
# Helper function definition with initial range set to (-infinity, +infinity)
function helper(node, lower, upper):
# Base case: If the current node is None, return True (it is a valid subtree)
if node == None:
return True

# Check if the current node's value is within the range (lower, upper)
if node.val <= lower or node.val >= upper:
return False

# Recursively validate the right subtree: range (node.val, upper)
if not helper(node.right, node.val, upper):
return False

# Recursively validate the left subtree: range (lower, node.val)
if not helper(node.left, lower, node.val):
return False

# If both subtrees are valid, return True
return True

# Initial call to the helper function with the root and the full range
return helper(root, -infinity, infinity)

Explanation of Detailed Steps

Main Function Call (
isValidBST

) : We start by calling the
isValidBST

function with the root node of the binary tree.
Helper Function Definition (
helper

) : Inside
isValidBST

, we define a nested
helper

function. The
helper

function is responsible for verifying the BST properties recursively for each subtree.
Base Case Check (
if node == None

) : If we reach a
None

node (indicating that we've traversed past a leaf node), the subtree is considered valid, and we return True.
Range Validation (
if node.val <= lower or node.val >= upper

) : We check if the current node’s value falls within the permissible bounds. If it doesn't, we return False immediately as it violates the BST condition.
Right Subtree Validation : The right subtree’s nodes should be greater than the current node's value. Therefore, we call
helper

on the right child with the node’s value as the new lower bound and the original upper bound.
Left Subtree Validation : The left subtree’s nodes should be less than the current node's value. Hence, we call
helper

on the left child with the node’s value as the new upper bound and the original lower bound.
Final Validation Check : If all recursive calls return True, the entire tree is considered a BST, and we return True from the
isValidBST

function.

By following these steps and the pseudocode provided, we can ensure that our solution correctly determines whether a given binary tree is a valid BST. This method ensures that we have an efficient and reliable way to check the BST properties across all nodes and subtrees of the binary tree.