Check if BST is valid or not

Problem Statement: Check if BST is valid or not

check BST: 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: root = [2,1,3]

Output: True

Approach 1: Brute Force

We need to check is the left subtree of a node contains any element greater than the node’s value and whether the right subtree of a node contains any element smaller than the node’s value.

We shall design two helper functions getMin(root) and getMax(root) which will get the minimum and maximum values of the tree with a given root. Then we will check :

If the node’s value is greater than the maximum value in the left subtree or not

The node’s value is lesser than the minimum value in the right subtree or not. Basically, we will check if this expression holds true or not: getMax(root.left) < root.val < getMin(root.right)

Time complexity will be O(n²) i.e. not the optimal one so we need to optimise it.

Approach 2: Using Inorder Traversal

We know that the inorder traversal of a binary search tree gives a sorted order of its elements. We shall use this to our advantage and traverse the tree in inorder fashion and store the elements in an array. We shall then traverse the array in a linear manner and check if its in sorted order or not.

class Solution {
private:
    TreeNode* prev = nullptr;

public:
    bool isValidBST(TreeNode* root) {
        return inorder(root);
    }

    bool inorder(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        if (!inorder(root->left)) {
            return false;
        }
        if (prev != nullptr && root->val <= prev->val) {
            return false;
        }
        prev = root;
        return inorder(root->right);
    }
};

import math
class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def isValidBST(self, root):

        def inorder(root):
            if not root:
                return True
            if not inorder(root.left):
                return False
            if root.val <= self.prev:
                return False
            self.prev = root.val
            return inorder(root.right)

        self.prev = -math.inf
        return inorder(root)
        
if __name__=='__main__':
    root = Node(12)
    root.left = Node(4)
    root.right = Node(25)
    root.left.left = Node(2)
    root.left.right = Node(9)
    root.right.left = Node(16)
    root.right.right = Node(32)
    
    root = Node(2)
    root.left = Node(1)
    root.right = Node(3)
    ob1 = Solution()
    print(ob1.isValidBST(root))

Time Complexity: O(n)

Space Complexity: O(n) for the space on the run-time stack.