Checking it the tree is BST via iterative way-CodePudding

Can anyone tell me why is this wrong?

Check for BST Iterative version.

101 out of 120 test cases have been passed

It fails for

10 5 18 2 9 15 19 N 4 8 N 1

this test case

class Solution
{
   public:
   //Function to check whether a Binary Tree is BST or not.
   bool isBST(Node* root) 
   {
       queue <Node*> q;
       q.push(root);
       while(!q.empty()){
           Node* temp = q.front();
           int key = temp->data;
           q.pop();
           if(temp->left){
               if(temp->left->data >= key){
                   return false;
               }
           }
           if(temp->right){
               if(temp->right->data <= key){
                   return false;
               }
           }
           if(temp->left)
               q.push(temp->left);
           if(temp->right)
               q.push(temp->right);
       }
       return true;
   }
};

CodePudding user response：

There is an article in geeksforgeeks that explains the algorithm step by step.


bool isValidBST(TreeNode* root) {
       stack<TreeNode* > Stack;
     
    // Stores previous visited node
    TreeNode* prev = NULL;
     
    // Traverse the binary tree
    while (!Stack.empty() ||
               root != NULL) {
 
        // Traverse left subtree
        while (root != NULL) {
 
            // Insert root into Stack
            Stack.push(root);
 
            // Update root
            root = root->left;
        }
 
        // Stores top element of Stack
        root = Stack.top();
 
        // Remove the top element of Stack
        Stack.pop();
 
        // If data value of root node less
        // than data value of left subtree
        if(prev != NULL &&
               root->val <= prev->val) {
            return false;
        }
 
        // Update prev
        prev = root;
 
        // Traverse right subtree
        // of the tree
        root = root->right;
    }
    return true;  
    }

CodePudding user response：

Can anyone tell me why is this wrong?

Your code only verifies that a node's right child has a value that is greater than the node's own value, but this is not enough. In a BST, not only the direct right child must be greater, but the whole subtree at the right side must consist of nodes that only have values that are greater.

For example, take the example tree you mentioned in your question:

      _ 10 _
     /      \
    5        18
  /   \     /  \
 2     9  15    19 
  \   /  /
   4 8  1

In this tree the node with value 1 violates the BST property, because it is less than 10. Your code only verifies that 1 is less than 15, but it should also have verified it is greater than 10.

The bread-first traversal which you have implemented with q, is not very suitable for solving this problem. If you want to stick with it, you have to push more to the queue than just node instances. You should push a window with min/max values between which the whole subtree of a given node must lie. So the queue should consist of triplets of (node, minValue, maxValue). Again, this is not the easiest way to solve this problem. Doing this with an in-order traversal is easier to implement.