Leet Code : Validate Binary Search Tree Java | CPP | Python solution

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.

Input: root = [2,1,3]
Output: true

Solution :

Java DFS :

class Solution {
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        doDFS(root, list);
        int size = list.size();
        for(int i=1; i<size; i++) {
            if(list.get(i-1) >= list.get(i))
                return false;
        }
        return true;
    }
    
    private void doDFS(TreeNode root, ArrayList<Integer> list) {
        if(root!=null) {
            doDFS(root.left, list);
            list.add(root.val);
            doDFS(root.right,list);
        }
        return;
    }
}

Python :

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = self.inorder(root, [])
        return True if res == sorted(res) and len(res) == len(set(res)) else False
    
    def inorder(self, root, res):
        if root:
            self.inorder(root.left, res)
            res.append(root.val)
            self.inorder(root.right , res)
        return res

CPP :

Inorder solution :

class Solution {
public:
    vector<int> v;
    void helper(TreeNode *root)
    {
        if(root == NULL)
            return;
        
        helper(root -> left);
        v.push_back(root -> val);
        helper(root -> right);
        
    }
    bool isValidBST(TreeNode* root) {
        
        helper(root);
        for(int i = 0 ; i < v.size() - 1; i++)
        {
            if(v[i] >= v[i + 1])
                return false;
        }
        return true;
    }
};