Why the solution for binary search tree validity is not working?

Question

I wrote a solution for checking the validity of the binary search tree using LinkedList and it's proving wrong information about the validity. I checked with a valid BST and it returns that the tree is not valid. The code is as following,

public static boolean isValidBST_( Node root ){

  boolean bol = false;
  LinkedList<Node> queue = new LinkedList<Node>();

  queue.add(root);

  while( !queue.isEmpty() ){

    Node cur = queue.poll();

    if ( ( cur.left != null && cur.data > cur.left.data ) || (cur.right != null && cur.data < cur.right.data  ) ){

      return bol;
    }

    if ( cur.left != null ){

       queue.offer(cur.left);
    }

    if ( cur.right != null ){

      queue.offer(cur.right);
    }

  } // WHILE


  if (queue.isEmpty() ){

    bol = true;
  }

  return bol;

}

How can I improve the code ?

I make the call from main as following,

public static void main (String[] args ){


 Node root = new Node(5);
 root.left = new Node(3);
 root.right = new Node(7); 


 root.left.left = new Node(1);
 root.left.right = new Node(4);

 root.right.left = new Node(6);
 root.right.right = new Node(9);

 System.out.println("Does the inserted BST is valid ?  Answer:  " + isValidBST_(root));

}

I thought I can iterate over the whole tree inside the while loop and be able to check whether the value of a node is larger than it's left node ( if exist ) and value of the node is smaller than it's right node ( if exist ). Thanks. — Monica Hübner
– Monica Hübner, Commented Nov 24, 2015 at 3:17

sprinter · Accepted Answer · 2015-11-24 03:47:56Z

1

You seem to have your checks the wrong way around:

if ( ( cur.left != null && cur.data > cur.left.data ) || (cur.right != null && cur.data < cur.right.data  ) )

will pass (and return false) when the node's data is greater than the left nodes data or smaller than the right node's data. You want the opposite. Try reversing the inequalities.

You asked 'how to improve the code'. This seems to be crying out for recursion:

boolean isValid(Node node) {
    if (node.left != null && (cur.data < node.left.data || !isValid(node.left)))
        return false;
    else if (node.right != null && (cur.data > node.right.data || !isValid(node.right)))
        return false;
    else
        return true;
}

If you want to stick with an iterative approach you can simplify by dropping your bol variable and removing the final check:

public boolean isValid(Node root) {
    LinkedList<Node> nodesToCheck = new LinkedList<>();
    nodesToCheck.offer(root);
    while (!nodesToCheck.isEmpty()) {
        Node current = nodesToCheck.poll();
        if (current.left != null) {
            if (current.data < current.left.data)
                return false;
            nodesToCheck.offer(current.left);
        }
        if (current.right != null) {
            if (current.data > current.right.data)
                return false;
            nodesToCheck.offer(current.right);
        }
    }
    return true;
}

edited Nov 24, 2015 at 3:47

answered Nov 24, 2015 at 3:15

sprinter

28.1k8 gold badges51 silver badges81 bronze badges

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

1 Comment

Monica Hübner Over a year ago

Thanks a lot, I find the answer and it's working. I wrote a recursive solution earlier and really want to write a solution simply iterate over the whole tree like this.

Collectives™ on Stack Overflow

Why the solution for binary search tree validity is not working?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related