Validate Binary Search Tree-1

Question

my solution failed for second example i dont know why, pls explain.

Here is the question:

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

Assume a 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 1:

                 2
                / \
               1   3

Input: [2,1,3]

Output: true

Example 2:

Input: [5,1,4,null,null,3,6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

  class Solution {
public:
    bool util(TreeNode*root,int minv=INT_MIN,int maxv=INT_MAX)
    { if(root==NULL)
        return true;
     if((root->val >= minv and root->val <= maxv) and 
util(root->left,minv,root->val)and util(root->right,root->val,maxv));
         return true;
 
     return false;
    }
    bool isValidBST(TreeNode* root) {
        return util(root);
    }
};

TheN00bBuilder TheN00bBuilder · Accepted Answer · 2021-03-03T05:04:03

One thing I'm seeing is that inside a binary search tree, all elements to the right of a node must be greater than the node. Your solution fails as 4 < 5, yet it is to the right. A simple solution would be to swap 4 and 5 in your second binary search tree.

EDIT: It may fit the definition of a binary tree after that swap, but it is not a good binary tree with that random 3 in the right subtree. A non-complete binary search tree does not need to be a balanced tree. Plugging in your set of numbers into something like VisuAlgo (https://visualgo.net/bn/bst) may be helpful in demonstrating how a binary search tree would look with that data, if you are still confused.

Validate Binary Search Tree-1

1 Answers