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

I did the same

I did this as well!

I used the same method like you, but I passed all solutons, but 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;

}

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.

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

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));
}

That should work if you are doing this for all nodes. Try checking if you are doing this for all nodes including subnodes, not just root. It might be sub-optimal though.

For completeness, I used a different approach. Think types of traversal and ordering.

i searched for the biggest item in the left tree and the smallest item in the right tree and compared them to the root. and did that in a recursive way for all sub nodes

What if there are parent and child with same values in them ... Ex:

                  10
                                             \
                                                 10

this code might not work then