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 · Accepted Answer · 2021-03-03 05:12:33Z

0

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.

edited Mar 3, 2021 at 5:12

answered Mar 3, 2021 at 5:04

TheN00bBuilder

1242 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

SAHIL GUPTA Over a year ago

i am asking that only that why is it failing for 4<5 i have included the statement that if root->val > root->right->val so return false thn why is it giving error

greybeard Over a year ago

It may fit the definition of a binary tree after [swapping node values 4 and 5] It does as before that swap. It fails being a BST, before & after.

Collectives™ on Stack Overflow

Validate Binary Search Tree-1

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related