Iterative Approach to Check if a Binary Tree is BST or Not

Intuition

The idea is to use something related to inorder traversal. As for a BST, its in-order traversal should give us a sorted array. Thus we will do something similar to it using a stack. Thus using a stack, we will perform the inorder traversal along the tree, but simultaneously, we will also maintain a ‘PREVIOUS’ pointer which will store the previously visited node during the inorder traversal and if at any point the current value of inorder traversal is less than the ‘PREVIOUS’ we will return false as then the binary tree cannot be BST. If we can perform a complete inorder traversal without violating the above condition, we will return true.

Things will become more clear from the following code.

Code

#include <iostream>
#include <stack>
using namespace std;

// Structure of a tree node.
class BinaryTreeNode
{
public:
   int data;
   BinaryTreeNode *left;
   BinaryTreeNode *right;

   // Constructor.
   BinaryTreeNode(int data)
   {
       this->data = data;
       left = NULL;
       right = NULL;
   }
};

// This function will check if the given Binary Tree is BST or not.
bool checkTreeIsBST(BinaryTreeNode *root)
{
   // Stack used for performing iterative inorder traversal.
   stack<BinaryTreeNode*> s1;

   // Stores previous visited node.
   BinaryTreeNode *previous = NULL;

   // Traverse the binary tree and perform Inorder traversal.
   while (s1.size() != 0 || root != NULL)
   {
       // Traverse left subtree.
       while (root != NULL)
       {
           // Insert root into ztack.
           s1.push(root);
           root = root->left;
       }

       root = s1.top();
       s1.pop();

       // If the value of root is less than 'PREVIOUS' value, then it cannot be BST. Thus we will return false.
       if (previous != NULL)
       {
           if (root->data <= previous->data)
           {
               return false;
           }
       }

       // Now root is our new 'PREVIOUS'
       previous = root;

       // Now right subtree will be traversed.
       root = root->right;
   }

   return true;
}

// Driver Code
int main()
{
   BinaryTreeNode *root = new BinaryTreeNode(10);
   root->left = new BinaryTreeNode(5);
   root->right = new BinaryTreeNode(12);
   root->left->left = new BinaryTreeNode(4);
   root->left->right = new BinaryTreeNode(6);
   root->right->right = new BinaryTreeNode(14);
   root->right->left = new BinaryTreeNode(11);

   cout << checkTreeIsBST(root);
}

You can also try this code with Online C++ Compiler

Run Code

Input

Output

1

Complexity Analysis

Time Complexity

O(N), where ‘N’ is the number of nodes in the tree.

As we are traversing every node in the tree only once.

Space Complexity

O(N), where ‘N’ is the number of nodes in the tree.

As we are using a stack to store ‘N’ nodes to perform the inorder traversal.

Frequently Asked Questions

What is the return type of the sumofSubtree function?

The return type of the sumofSubtree function is the integral pair. In C++, pair is a type of container which is present in STL, and one can store any kind of data in the form of pair in this.

What is a Subtree in a binary tree?

In a Binary tree, a subtree of a node is recognized as another binary tree whose root node is that particular node. In a Binary tree, there are two types of subtrees

• Left Subtree
• Right Subtree

Note:- The value of subtree can be Null also.

In what order is the inorder traversal of the Binary Search Tree Obtained?

The Inorder Traversal of Binary Search Tree has the values of nodes arranged in Ascending Order.

Conclusion

We saw how we could solve the problem ‘check if a binary tree is BST or not’ iteratively using the in-order traversal implemented by stack for iterative purposes. Now, Binary Trees and BST are wide topics and are equally important. 

Recommended Problems:

• Burn Tree
• Size of largest BST in a Binary Tree.
• Partial BST
   

Recommended Reading:

• Check for Children Sum Property in Binary Tree
• Check if all Leaves are at the Same Level
• Check if the Given Binary Tree is A Subtree of Another Binary Tree
• Check if Binary Tree Contains a Balanced BST of Size K
• Check if Array Represents Inorder of BST
• Row WIth Maximum Number of 1s
• Traverse A BST in Min-Max Manner
• Find the Predecessor and Successor of all Nodes in a BST

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.