Does that mean the child nodes must not be equal to the current node?

thanks a lot, 3, 6, 7 were failing because of this issue.

Thanks much.. Solved my errors

breh

Thanks a lot mark, saved me lot of time. This should have been mentioned in the problem.

THIS IS MY SOLUTION

int recent ;

boolean checkBST(Node root) { if(root == null) return true ;

boolean flag = checkBST(root.left) ;    

if(flag) {
    if(recent >= root.data) 
        return false ;
    else 
        recent = root.data ;
}

if(flag)
    flag = checkBST(root.right) ;

return flag ;

}

Yeah thanx alot some test case were failing because of it

get score 20.77......this code!

boolean checkBST(Node root) {
   return false;
}

great advice!

Yes.

A single line like below will pass these cases, thanks for saving my time.

    if(node.data <= min || node.data >= max) return false;

thanks ! that helped!!

Thanks man..i had this issue with 3,6,7

the actual definition of BST allows duplicate values, as long as their inorder walk is non-decreasing, so that requirement in this problem is actually wrong.

facepalm

Inorder Solution

https://youtu.be/cLZa4zzt1E8

Well Explained !

That's because the question states:

1.The value of every node in a node's left subtree is less than the data value of that node.

2.The value of every node in a node's right subtree is greater than the data value of that node.

This means duplicate values are not permitted in a valid tree, so you need to return false if you encounter any.

Thanks :D I was wondering why 3 cases failed

I must agree. Not knowing how the tree was constructed based on the input - how it sets the root etc, made it difficult for me. Perhaps it was explained in a previous challenge somewhere but I did not find that.

Could anyone take some time and help me/others to understand the construction of the tree for the testcase.

2

1 2 4 3 5 6 7

Is the below correct? But the expected output is NO. So just like to check with you all.

1
    2
        4
    3       5
                6
                    7

This is a valid BST right?

I did the same

I did this as well!

I used the same method like you, but I passed all solutons. However, I have no idea why my recusive method can't pass all.

no need for a traversal. Take the node->data of each node directly from the vector values given in private. Rest logic is spot on. Did the same :)

I did a similar thing (except that the list was in descending order). My recursive algorithm had a flaw that appeared to be too difficult to waste time fixing.

Note that I am more used to C so I didn't bother with the C++ libraries.

    struct List {
        int data;
        List *next;
    };

    List *makeDescendingList(Node *head, List *list) {
        List *newListNode;
        if (head == NULL) {
            return list;
        } else {
            list = makeDescendingList(head->left, list);
            newListNode = new(List);
            newListNode->data = head->data;
            newListNode->next = list;
            return makeDescendingList(head->right, newListNode);
        } 
    }

    bool isDescendingList (List *list) {
        while (list != NULL) {
            if (list->next != NULL && list->data <= list->next->data) {
                return false;
            }
            list = list->next;
        }
        return true;
    }
    
	bool checkBST(Node* root) {
		return isDescendingList(makeDescendingList(root, NULL));
	}

Inorder traversal of BST is always sorted. So you don't have to put elements into list. Store maximum element so far in a variable (say maxSoFar) and then just check if currentNode.data <= maxSoFar. It'll save you from iterating list.

i tried same thing but many test cases fails... help me to come out plz.

I also did the same but some test cases are not working .Here my code- bool func(vector v) { int count=0; for(int i=0;i v; if(root==NULL) return true; if(root!=NULL) { checkBST(root->left); v.push_back(root->data); checkBST(root->right); } return func(v);

}

did the same dude !!!!!! 2 cases failed in recursion,didn't know the reason and sample input was also confusing and accidentally i reached this solution while understanding the sample input ... ;)

You don't need to create list or array while doing inorder traversal. The whole point is to compare current and last element, if last elment is greater or equal to current return false. Just use one wrapper int, or Integer static variable to keep track of last visited.

I think you can improve your space complexity only using a variable and comparing current node with his prev node.

Was able to solve it because of your comment. thanks a lot. Here's my code.

static ArrayList<Integer> list = new ArrayList<Integer>();
    boolean checkBST(Node root) {
        
        inOrder(root);
        
        for(int i = 1; i< list.size(); i++){
            if(list.get(i)<=list.get(i-1))
                return false;
        }
        return true;
         
    }
    
    void inOrder(Node root){
        if(root == null)
            return;
        inOrder(root.left);
        list.add(root.data);
        inOrder(root.right);
    }

Did the same thing.

I did the same. But it's not working.

Here is my code. Can you review it please?

vector <int> inorder_nodes;

void Traverse_Inorder(Node *root)
{
    if(root->left != NULL)
        Traverse_Inorder(root->left);

    inorder_nodes.push_back(root->data);

    if(root->right != NULL)
        Traverse_Inorder(root->right);        
}

bool checkBST(Node* root) {

    bool result=true;

    Traverse_Inorder(root);

    for (int i = 0; i < inorder_nodes.size(); i++)
    {
        if(inorder_nodes[i] > inorder_nodes[i+1])
        {
            result = false;
            break;
        }            
    }

    return result;

}

Isn't necessary to store the values in a list, just keep track of the previous visited value (inorder sequence), and if your current visiting value is less than it means that isn't a BST

Finally I got my mistake!!

This is clean and easy to understand!

You can change the last if condition via DeMorgan's law to make this even simpler!

boolean checkBST(Node root, int min, int max) {
    if (root == null) return true; 

    if (root.data <= min || root.data >= max)
        return false;

    return checkBST(root.left, min, root.data) && checkBST(root.right, root.data, max));
        
}

This code will fail if there is a single node tree with value as Integer.MIN_VALUE or Integer.MAX_VALUE

@jckarlos921 Its failing for 7th test case.. But I have the same solution too... Even in forums the same approach is used.. U have any idea ?

Love your answer and love you also

yes, i am getting the same error. did you figure it out.

Some issue with Java 8 option. Try Java 7.

Same error. Hacker Rank pls fix it

nice solution bro...keep it up!

Super elegant

same here bro..but it is giving compilation error..no inorder function found

Slightly shorter but otherwise the same:

boolean checkBST(Node root) {
      return checkBSTRecur(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean checkBSTRecur(
    Node curNode, long lowerBound, long upperBound){
  return curNode == null ||
	(lowerBound < curNode.data && curNode.data < upperBound
         && checkBSTRecur(curNode.left, lowerBound, curNode.data)
         && checkBSTRecur(curNode.right, curNode.data, upperBound));
}