1
\$\begingroup\$

I have a function that takes the root node as input and needs to return if the tree is a proper BST as per the definition below:

  • The data value of every node in a node's left subtree is less than the data value of that node.
  • The data value of every node in a node's right subtree is greater than the data value of that node
  • It cannot contain duplicate values.

Here's my implementation

  boolean checkBST(Node root) {        
        if(root==null) return false;
        Queue<Node> q = new LinkedList<>();
        Set<Integer> s = new HashSet<>();
        q.add(root);       
        while(q.size()>0){   
            Node t = q.poll();
            if(s.contains(t.data))
                return false;
            s.add(t.data);
            if(t.left!=null)
                {
                    if(t.data<=t.left.data)
                        return false;
                q.offer(t.left);
            }
            if(t.right!=null){
                if(t.data>=t.right.data)
                    return false;
                q.offer(t.right);
            }
        }
        return true;   
    }

Things to discuss:

  • I've pursued a Breadth first approach. Is there a better approach?
  • The above procedure fails for some test inputs (I don't know what the inputs are that breaks it). Trying to find out what they are
  • Issues with the above implementation
\$\endgroup\$

closed as off-topic by Graipher, mdfst13, alecxe, Mathieu Guindon Apr 16 '17 at 13:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Graipher, mdfst13, alecxe, Mathieu Guindon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ Failing test case: root is 10. root.left is 5. root.left.right is 11. All others are null. This tree is not a valid BST by your definition (11 is not less than 10), but it will pass your test. Because 11 is greater than 5 and 5 is less than 10. \$\endgroup\$ – mdfst13 Apr 8 '17 at 17:39
4
\$\begingroup\$

Since @Imus has already pointed out the technical problems with your code, and how a depth-first approach is more reasonable, I'll just note on code style and give a few bits of advice.

Advice

If you expect balanced BSTs of height > 11 (more than 6500 nodes), to avoid stack overflow errors you can still use a DFS with an explicit Stack and while loop, like you do for your BFS - it'll even be less code.

Style

Note that here all my points can be seen in example in @Imus' answer.

  1. Spaces around operators make expressions easier to read.

  2. Consistent bracing style and indentation. I prefer the opening brace to be on the same line as the statement, with a space between the closing parenthesis and the opening brace. The closing brace should be on its own line.

  3. Horrible variable names - one-letter names are reserved for loop indices, and then too not always. Variable names should be meaningful and convey the purpose of the variable. Use visitedNodes instead of q, processedContents instead of s, and currentNode instead of t. Doesn't it make it that much more understandable at first glance?

  4. !visitedNodes.isEmpty() looks a bit better than q.size()>0 in your while loop.

  5. My recommendation is to always use the block form instead of the statement form for if/else statements or for loops (use braces around even single-line bodies). This makes code addition later easier, and also contributes to readability.

Everything in points 1 to 3 can be done automatically by a proper IDE (you'll have to choose the good names, the IDE will suggest them to you after that so you don't need to type as much).

\$\endgroup\$
  • \$\begingroup\$ Nice complementary answer and thank you for the edits on mine. +1 :) \$\endgroup\$ – Imus Apr 12 '17 at 11:10
  • \$\begingroup\$ I doubt the stack + while solution would be less code though ;) But correct to be safer against stack overflows and probably more memory efficient overall. (java doesn't really optimise for recursive calls). \$\endgroup\$ – Imus Apr 12 '17 at 11:16
  • \$\begingroup\$ @Imus but the recursive solution is more readable in the general case - and that is what is most important during education. Plus, he'd need some 2^12 nodes before he'd have to consider a stack overflow, but there is an exponential blowup in memory consumption. Also, the iterative DFS will be equal to or less in code than the BFS - as you said, they're almost equivalent for a BST. \$\endgroup\$ – Tamoghna Chowdhury Apr 12 '17 at 15:07
3
\$\begingroup\$

The mistake you made in your implementation is that you check for each node if the direct child nodes are smaller (left) and larger (right). However, this isn't enough.

You need to check if the current node's content is larger than those of all the nodes in its left subtree. This can be simplified to checking if its content is larger than that of the node with the greatest content in the left subtree. Assuming the left node is ordered (you check this anyway), you can just find the rightmost child node of the left child.

Then you have to similarly check if the current node's content is smaller than all nodes of its right subtree, which can be simplified into checking that the content of the current node is smaller than the content of the leftmost child of its right child node, which is the node in question.

Breadth-First Search (BFS) and Depth-First Search (DFS) are quite similar for a binary search tree, however, a DFS can be easier to implement since recursion can be used instead of an explicit queue. The basic idea on how to do so is:

public boolean checkBST(Node node) {
    if(node == null || isLeafNode(node){
        return true;
    }
    if(!checkBST(node.left)){
        return false;
    }
    if(!checkBST(node.right)){
        return false;
    }
    if(node.getValue() < max(node.left)){
        return false;
    }
    if(node.getValue() > min(node.right)){
        return false;
    }
    return true;
}

All you need here is to implement isLeafNode, min and max methods. min returns the node with the smallest content among the subtrees of the current node, max finds the one with the greatest content.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.