Open In App

A program to check if a Binary Tree is BST or not

Last Updated : 04 Jun, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

A Binary Search Tree (BST) is a node-based binary tree data structure that has the following properties. 

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
  • Each node (item in the tree) has a distinct key.
Change

Binary Search Tree

Recommended Practice

Naive Approach:

The idea is to for each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node. 

Follow the below steps to solve the problem:

  • If the current node is null then return true
  • If the value of the left child of the node is greater than or equal to the current node then return false
  • If the value of the right child of the node is less than or equal to the current node then return false
  • If the left subtree or the right subtree is not a BST then return false
  • Else return true

Below is the implementation of the above approach:

C++
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

int maxValue(struct node* node)
{
    if (node == NULL) {
        return INT16_MIN;
    }
    int value = node->data;
    int leftMax = maxValue(node->left);
    int rightMax = maxValue(node->right);

    return max(value, max(leftMax, rightMax));
}

int minValue(struct node* node)
{
    if (node == NULL) {
        return INT16_MAX;
    }
    int value = node->data;
    int leftMax = minValue(node->left);
    int rightMax = minValue(node->right);

    return min(value, min(leftMax, rightMax));
}

/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node)
{
    if (node == NULL)
        return 1;

    /* false if the max of the left is > than us */
    if (node->left != NULL
        && maxValue(node->left) >= node->data)
        return 0;

    /* false if the min of the right is <= than us */
    if (node->right != NULL
        && minValue(node->right) <= node->data)
        return 0;

    /* false if, recursively, the left or right is not a BST
     */
    if (!isBST(node->left) || !isBST(node->right))
        return 0;

    /* passing all that, it's a BST */
    return 1;
}

/* Driver code*/
int main()
{
    struct node* root = newNode(4);
    root->left = newNode(2);
    root->right = newNode(5);
    // root->right->left = newNode(7);
    root->left->left = newNode(1);
    root->left->right = newNode(3);

    // Function call
    if (isBST(root))
        printf("Is BST");
    else
        printf("Not a BST");

    return 0;
}
// this code rectify by Laijyour Luv
C
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

int maxValue(struct node* node)
{
    if (node == NULL) {
        return 0;
    }

    int leftMax = maxValue(node->left);
    int rightMax = maxValue(node->right);

    int value = 0;
    if (leftMax > rightMax) {
        value = leftMax;
    }
    else {
        value = rightMax;
    }

    if (value < node->data) {
        value = node->data;
    }

    return value;
}

int minValue(struct node* node)
{
    if (node == NULL) {
        return 1000000000;
    }

    int leftMax = minValue(node->left);
    int rightMax = minValue(node->right);

    int value = 0;
    if (leftMax < rightMax) {
        value = leftMax;
    }
    else {
        value = rightMax;
    }

    if (value > node->data) {
        value = node->data;
    }

    return value;
}

/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node)
{
    if (node == NULL)
        return 1;

    /* false if the max of the left is > than us */
    if (node->left != NULL
        && maxValue(node->left) > node->data)
        return 0;

    /* false if the min of the right is <= than us */
    if (node->right != NULL
        && minValue(node->right) < node->data)
        return 0;

    /* false if, recursively, the left or right is not a BST
     */
    if (!isBST(node->left) || !isBST(node->right))
        return 0;

    /* passing all that, it's a BST */
    return 1;
}

/* Driver code*/
int main()
{
    struct node* root = newNode(4);
    root->left = newNode(5);
    root->right = newNode(6);
   // root->left->left = newNode(1);
    //root->left->right = newNode(3);

    // Function call
    if (isBST(root))
        printf("Is BST");
    else
        printf("Not a BST");

    getchar();
    return 0;
}
Java
// Java program to check if a given tree is BST.
import java.io.*;

/* A binary tree node has data, pointer to
left child and a pointer to right child */
class Node {
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};

public class GFG {
    static int maxValue(Node node)
    {
        if (node == null) {
            return Integer.MIN_VALUE;
        }
        int value = node.data;
        int leftMax = maxValue(node.left);
        int rightMax = maxValue(node.right);

        return Math.max(value, Math.max(leftMax, rightMax));
    }

    static int minValue(Node node)
    {
        if (node == null) {
            return Integer.MAX_VALUE;
        }
        int value = node.data;
        int leftMax = minValue(node.left);
        int rightMax = minValue(node.right);

        return Math.min(value, Math.min(leftMax, rightMax));
    }

    /* Returns true if a binary tree is a binary search tree
     */
    static boolean isBST(Node node)
    {
        if (node == null) {
            return true;
        }

        /* false if the max of the left is > than us */
        if (node.left != null
            && maxValue(node.left) > node.data) {
            return false;
        }

        /* false if the min of the right is <= than us */
        if (node.right != null
            && minValue(node.right) < node.data) {
            return false;
        }

        /* false if, recursively, the left or right is not a
         * BST*/
        if (isBST(node.left) == false
            || isBST(node.right) == false) {
            return false;
        }

        /* passing all that, it's a BST */
        return true;
    }

    public static void main(String[] args)
    {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);

        // root->right->left = newNode(7);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        // Function call
        if (isBST(root)) {
            System.out.print("Is BST");
        }
        else {
            System.out.print("Not a BST");
        }
    }
}
Python
# Python program to check if a binary tree is bst or not
# A binary tree node has data, pointer to left child
# and a pointer to right child
class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def maxValue(node):
    if node is None:
        return 0;
    
    leftMax = maxValue(node.left)
    rightMax = maxValue(node.right)
    
    value = 0;
    if leftMax > rightMax:
        value = leftMax
    else:
        value = rightMax
    
    if value < node.data:
        value = node.data
    
    return value
    
def minValue(node):
    if node is None:
        return 1000000000
    
    leftMax = minValue(node.left)
    rightMax = minValue(node.right)
    
    value = 0
    if leftMax < rightMax:
        value = leftMax
    else:
        value = rightMax
    
    if value > node.data:
        value = node.data
    
    return value

# Returns true if a binary tree is a binary search tree
def isBST(node):
    if node is None:
        return True
    
    # false if the max of the left is > than us
    if(node.left is not None and maxValue(node.left) > node.data):
        return False
    
    # false if the min of the right is <= than us
    if(node.right is not None and minValue(node.right) < node.data):
        return False
    
    #false if, recursively, the left or right is not a BST
    if(isBST(node.left) is False or isBST(node.right) is False):
        return False
    
    # passing all that, it's a BST
    return True

# Driver code
if __name__ == "__main__":
  root = Node(4)
  root.left = Node(2)
  root.right = Node(5)
  # root.right.left = Node(7)
  root.left.left = Node(1)
  root.left.right = Node(3)

  # Function call
  if isBST(root) is True:
      print("Is BST")
  else:
      print("Not a BST")

# This code is contributed by Yash Agarwal(yashagarwal2852002)
C#
using System;
using System.Linq;
using System.Collections.Generic;

class GFG {
    
    /* A binary tree node has data, pointer to left child
    and a pointer to right child */
    class node {
        public int data; 
        public node left, right;
    };
    
    /* Helper function that allocates a new node with the
    given data and null left and right pointers. */
    static node newNode(int data) 
    { 
        node node = new node(); 
        node.data = data; 
        node.left = null;
        node.right = null; 
        return node; 
    }
    
    static int maxValue( node node)
    {
        if (node == null) {
            return Int16.MinValue;
        }
        int value = node.data;
        int leftMax = maxValue(node.left);
        int rightMax = maxValue(node.right);
    
        return Math.Max(value, Math.Max(leftMax, rightMax));
    }
    
    static int minValue( node node)
    {
        if (node == null) {
            return Int16.MaxValue;
        }
        int value = node.data;
        int leftMax = minValue(node.left);
        int rightMax = minValue(node.right);
    
        return Math.Min(value, Math.Min(leftMax, rightMax));
    }
    
    /* Returns true if a binary tree is a binary search tree */
    static int isBST( node node)
    {
        if (node == null)
            return 1;
    
        /* false if the max of the left is > than us */
        if (node.left != null
            && maxValue(node.left) > node.data)
            return 0;
    
        /* false if the min of the right is <= than us */
        if (node.right != null
            && minValue(node.right) < node.data)
            return 0;
    
        /* false if, recursively, the left or right is not a BST
         */
        if (isBST(node.left)==0 || isBST(node.right)==0)
            return 0;
    
        /* passing all that, it's a BST */
        return 1;
    }
    
    /* Driver code*/
    public static void Main()
    {
        node root = newNode(4);
        root.left = newNode(2);
        root.right = newNode(5);
        // root.right.left = newNode(7);
        root.left.left = newNode(1);
        root.left.right = newNode(3);
    
        // Function call
        if (isBST(root)==1)
            Console.Write("Is BST");
        else
            Console.Write("Not a BST");
    
    }
}
Javascript
// JavaScript Program for the above approach

// A binary tree node has data, pointer to left child
// and a pointer to right child
class Node{
    constructor(data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
function newNode(data){
    let node = new Node(data);
    return node;
}

function maxValue(node){
    if(node == null) return Number.MIN_VALUE;
    
    let value = node.data;
    let leftMax = maxValue(node.left);
    let rightMax = maxValue(node.right);
    
    return Math.max(value, Math.max(leftMax, rightMax));
}

function minValue(node){
    if(node == null) return Number.MAX_VALUE;
    
    let value = node.data;
    let leftMax = minValue(node.left);
    let rightMax = minValue(node.right);
    
    return Math.min(value, Math.min(leftMax, rightMax));
}

// Returns true if a binary tree is a binary search tree
function isBST(node){
    if(node == null) return 1;
    
    // false if the max of the left is > than us
    if(node.left != null && maxValue(node.left) > node.data)
        return 0;
    
    // false if the min of the right is <= than us
    if(node.right != null && minValue(node.right) < node.data)
        return 0;
        
    // false if, recursively, the left or right is not a BST
    if(!isBST(node.left) || !isBST(node.right))
        return 0;
        
    // passing all that, it's a BST
    return 1;
}

// Driver code
let root = newNode(4);
root.left = newNode(2)
root.right = newNode(5)

// root.right.left = Node(7)
root.left.left = newNode(1)
root.left.right = newNode(3)

// Function call
if(isBST(root))
    console.log("Is BST");
else
    console.log("Not a BST");

// This code is contributed by Yash Agarwal(yashagarwal2852002)

Output
Is BST

Note: It is assumed that you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree

Time Complexity: O(N2), As we visit every node just once and our helper method also takes O(N) time, so overall time complexity becomes O(N) * O(N) = O(N2)
Auxiliary Space: O(H), Where H is the height of the binary tree, and the extra space is used due to the function call stack.

Check BST using specified range of minimum and maximum values of nodes:

The isBSTUtil() function is a recursive helper function that checks whether a subtree (rooted at a given node) is a BST within the specified range of minimum (min) and maximum (max) values. If any node violates this range, the function returns false; otherwise, it continues checking the left and right subtrees.

Below is the implementation of the above approach: 

C++
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data,
pointer to left child and
a pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;

    /* Constructor that allocates
    a new node with the given data
    and NULL left and right pointers. */
    node(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int isBSTUtil(node* node, int min, int max);

/* Returns true if the given
tree is a binary search tree
(efficient version). */
int isBST(node* node)
{
    return (isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given
tree is a BST and its values
are >= min and <= max. */
int isBSTUtil(node* node, int min, int max)
{
    /* an empty tree is BST */
    if (node == NULL)
        return 1;

    /* false if this node violates
    the min/max constraint */
    if (node->data < min || node->data > max)
        return 0;

    /* otherwise check the subtrees recursively,
    tightening the min or max constraint */
    return isBSTUtil(node->left, min, node->data - 1)
      
           && // Allow only distinct values
           isBSTUtil(node->right, node->data + 1,
                     max); // Allow only distinct values
}

/* Driver code*/
int main()
{
    node* root = new node(4);
    root->left = new node(2);
    root->right = new node(5);
    root->left->left = new node(1);
    root->left->right = new node(3);

      // Function call
    if (isBST(root))
        cout << "Is BST";
    else
        cout << "Not a BST";

    return 0;
}

// This code is contributed by rathbhupendra
C
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};

int isBSTUtil(struct node* node, int min, int max);

/* Returns true if the given tree is a binary search tree
 (efficient version). */
int isBST(struct node* node)
{
    return (isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given tree is a BST and its
   values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max)
{
    /* an empty tree is BST */
    if (node == NULL)
        return 1;

    /* false if this node violates the min/max constraint */
    if (node->data < min || node->data > max)
        return 0;

    /* otherwise check the subtrees recursively,
     tightening the min or max constraint */
    return isBSTUtil(node->left, min, node->data - 1)
           && // Allow only distinct values
           isBSTUtil(node->right, node->data + 1,
                     max); // Allow only distinct values
}

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

/* Driver code*/
int main()
{
    struct node* root = newNode(4);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(3);

      // Function call
    if (isBST(root))
        printf("Is BST");
    else
        printf("Not a BST");

    getchar();
    return 0;
}
Java
// Java implementation to check if given Binary tree
// is a BST or not

/* Class containing left and right child of current
 node and key value*/
class Node {
    int data;
    Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    // Root of the Binary Tree
    Node root;

    /* Can give min and max value according to your code or
    can write a function to find min and max value of tree.
  */

    /* Returns true if given search tree is binary
     search tree (efficient version) */
    boolean isBST()
    {
        return isBSTUtil(root, Integer.MIN_VALUE,
                         Integer.MAX_VALUE);
    }

    /* Returns true if the given tree is a BST and its
      values are >= min and <= max. */
    boolean isBSTUtil(Node node, int min, int max)
    {
        /* an empty tree is BST */
        if (node == null)
            return true;

        /* false if this node violates the min/max
         * constraints */
        if (node.data < min || node.data > max)
            return false;

        /* otherwise check the subtrees recursively
        tightening the min/max constraints */
        // Allow only distinct values
        return (
            isBSTUtil(node.left, min, node.data - 1)
            && isBSTUtil(node.right, node.data + 1, max));
    }

    /* Driver code */
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(4);
        tree.root.left = new Node(2);
        tree.root.right = new Node(5);
        tree.root.left.left = new Node(1);
        tree.root.left.right = new Node(3);

          // Function call
        if (tree.isBST())
            System.out.println("Is BST");
        else
            System.out.println("Not a BST");
    }
}
Python
# Python program to check if a binary tree is bst or not

INT_MAX = 4294967296
INT_MIN = -4294967296

# A binary tree node


class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


# Returns true if the given tree is a binary search tree
# (efficient version)
def isBST(node):
    return (isBSTUtil(node, INT_MIN, INT_MAX))

# Returns true if the given tree is a BST and its values
# >= min and <= max


def isBSTUtil(node, mini, maxi):

    # An empty tree is BST
    if node is None:
        return True

    # False if this node violates min/max constraint
    if node.data < mini or node.data > maxi:
        return False

    # Otherwise check the subtrees recursively
    # tightening the min or max constraint
    return (isBSTUtil(node.left, mini, node.data - 1) and
            isBSTUtil(node.right, node.data+1, maxi))


# Driver code
if __name__ == "__main__":
  root = Node(4)
  root.left = Node(2)
  root.right = Node(5)
  root.left.left = Node(1)
  root.left.right = Node(3)

  # Function call
  if (isBST(root)):
      print("Is BST")
  else:
      print("Not a BST")

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;

// C# implementation to check if given Binary tree
// is a BST or not

/* Class containing left and right child of current
 node and key value*/
public class Node {
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    // Root of the Binary Tree
    public Node root;

    /* can give min and max value according to your code or
    can write a function to find min and max value of tree.
  */

    /* returns true if given search tree is binary
     search tree (efficient version) */
    public virtual bool BST
    {
        get
        {
            return isBSTUtil(root, int.MinValue,
                             int.MaxValue);
        }
    }

    /* Returns true if the given tree is a BST and its
      values are >= min and <= max. */
    public virtual bool isBSTUtil(Node node, int min,
                                  int max)
    {
        /* an empty tree is BST */
        if (node == null) {
            return true;
        }

        /* false if this node violates the min/max
         * constraints */
        if (node.data < min || node.data > max) {
            return false;
        }

        /* otherwise check the subtrees recursively
        tightening the min/max constraints */
        // Allow only distinct values
        return (
            isBSTUtil(node.left, min, node.data - 1)
            && isBSTUtil(node.right, node.data + 1, max));
    }

    /* Driver code */
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(4);
        tree.root.left = new Node(2);
        tree.root.right = new Node(5);
        tree.root.left.left = new Node(1);
        tree.root.left.right = new Node(3);
      
        // Function call
        if (tree.BST) {
            Console.WriteLine("IS BST");
        }
        else {
            Console.WriteLine("Not a BST");
        }
    }
}

// This code is contributed by Shrikant13
Javascript
// Javascript implementation to 
// check if given Binary tree
// is a BST or not
 
/* Class containing left and right child of current
 node and key value*/

class Node
{
    constructor(item)
    {
        this.data=item;
        this.left=this.right=null;
    }
}

 //Root of the Binary Tree
    let root;
    
    /* can give min and max value according to your code or
    can write a function to find min and max value of tree. */
 
    /* returns true if given search tree is binary
     search tree (efficient version) */
    function isBST()
    {
        return isBSTUtil(root, Number.MIN_VALUE,
                               Number.MAX_VALUE);
    }
    
    /* Returns true if the given tree is a BST and its
      values are >= min and <= max. */
    function isBSTUtil(node,min,max)
    {
        /* an empty tree is BST */
        if (node == null)
            return true;
 
        /* false if this node violates 
        the min/max constraints */
        if (node.data < min || node.data > max)
            return false;
 
        /* otherwise check the subtrees recursively
        tightening the min/max constraints */
        // Allow only distinct values
        return (isBSTUtil(node.left, min, node.data-1) &&
                isBSTUtil(node.right, node.data+1, max));
    }
    
     /* Driver program to test above functions */
        root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
 
        if (isBST())
            console.log("IS BST<br>");
        else
            console.log("Not a BST<br>");

// This code is contributed by rag2127

Output
Is BST

Time Complexity: O(N), Where N is the number of nodes in the tree
Auxiliary Space: O(1), if Function Call Stack size is not considered, otherwise O(H) where H is the height of the tree

Check BST using Inorder Traversal:

The idea is to use Inorder traversal of a binary search tree generates output, sorted in ascending order. So generate inorder traversal of the given binary tree and check if the values are sorted or not

Follow the below steps to solve the problem:

  • Do In-Order Traversal of the given tree and store the result in a temp array. 
  • Check if the temp array is sorted in ascending order, if it is, then the tree is BST.

Note: We can avoid the use of an Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited nodes. If the value of the currently visited node is less than the previous value, then the tree is not BST.

Below is the implementation of the above approach:

C++
// C++ program to check if a given tree is BST.
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
    int data;
    struct Node *left, *right;

    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};

bool isBSTUtil(struct Node* root, Node*& prev)
{
    // traverse the tree in inorder fashion and
    // keep track of prev node
    if (root) {
        if (!isBSTUtil(root->left, prev))
            return false;

        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
            return false;

        prev = root;

        return isBSTUtil(root->right, prev);
    }

    return true;
}

bool isBST(Node* root)
{
    Node* prev = NULL;
    return isBSTUtil(root, prev);
}

/* Driver code*/
int main()
{
    struct Node* root = new Node(3);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(1);
    root->left->right = new Node(4);

    // Function call
    if (isBST(root))
        cout << "Is BST";
    else
        cout << "Not a BST";

    return 0;
}
Java
// Java program to check if a given tree is BST.
import java.io.*;

class GFG {
    /* A binary tree node has data, pointer to
    left child and a pointer to right child */
    public static class Node {
        public int data;
        public Node left, right;

        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }
    };

    static Node prev;

    static Boolean isBSTUtil(Node root)
    {
        // traverse the tree in inorder fashion and
        // keep track of prev node
        if (root != null) {
            if (!isBSTUtil(root.left))
                return false;

            // Allows only distinct valued nodes
            if (prev != null && root.data <= prev.data)
                return false;

            prev = root;

            return isBSTUtil(root.right);
        }
        return true;
    }

    static Boolean isBST(Node root)
    {
        return isBSTUtil(root);
    }

    // Driver Code
    public static void main(String[] args)
    {
        Node root = new Node(3);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(4);

        // Function call
        if (isBST(root))
            System.out.println("Is BST");
        else
            System.out.println("Not a BST");
    }
}

// This code is contributed by Shubham Singh
Python
# Python3 program to check
# if a given tree is BST.
import math

# A binary tree node has data,
# pointer to left child and
# a pointer to right child
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def isBSTUtil(root, prev):

    # traverse the tree in inorder fashion
    # and keep track of prev node
    if (root != None):
        if (isBSTUtil(root.left, prev) == False):
            return False

        # Allows only distinct valued nodes
        if (prev != None and
                root.data <= prev.data):
            return False

        prev = root
        return isBSTUtil(root.right, prev)

    return True


def isBST(root):
    prev = None
    return isBSTUtil(root, prev)


# Driver Code
if __name__ == '__main__':
    root = Node(3)
    root.left = Node(2)
    root.right = Node(5)
    root.right.left = Node(1)
    root.right.right = Node(4)

    # Function call
    if (isBST(root) == None):
        print("Is BST")
    else:
        print("Not a BST")

# This code is contributed by Srathore
C#
// C# program to check if a given tree is BST.
using System;
public class GFG {
    /* A binary tree node has data, pointer to
    left child and a pointer to right child */
    public class Node {
        public int data;
        public Node left, right;

        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }
    };

    static Node prev;

    static Boolean isBSTUtil(Node root)
    {
        // traverse the tree in inorder fashion and
        // keep track of prev node
        if (root != null) {
            if (!isBSTUtil(root.left))
                return false;

            // Allows only distinct valued nodes
            if (prev != null && root.data <= prev.data)
                return false;

            prev = root;

            return isBSTUtil(root.right);
        }
        return true;
    }

    static Boolean isBST(Node root)
    {
        return isBSTUtil(root);
    }

    // Driver Code
    public static void Main(String[] args)
    {
        Node root = new Node(3);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(4);

        // Function call
        if (isBST(root))
            Console.WriteLine("Is BST");
        else
            Console.WriteLine("Not a BST");
    }
}

// This code is contributed by Rajput-Ji
Javascript
// Javascript program to check if a given tree is BST.    
    class Node
    {
        constructor(data)
        {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
    
    let prev;
 
    function isBSTUtil(root)
    {
    
        // traverse the tree in inorder fashion and
        // keep track of prev node
        if (root != null)
        {
            if (!isBSTUtil(root.left))
                return false;

            // Allows only distinct valued nodes
            if (prev != null && root.data <= prev.data)
                return false;

            prev = root;

            return isBSTUtil(root.right);
        }
        return true;
    }

    function isBST(root)
    {
        return isBSTUtil(root);
    }
    
    let root = new Node(3);
    root.left = new Node(2);
    root.right = new Node(5);
    root.left.left = new Node(1);
    root.left.right = new Node(4);
 
    if (isBST(root))
        console.log("Is BST");
    else
        console.log("Not a BST");

// This code is contributed by divyeshrabadiya07.

Output
Not a BST

Time Complexity: O(N), Where N is the number of nodes in the tree
Auxiliary Space: O(H), Here H is the height of the tree and the extra space is used due to the function call stack. 

Check BST using Morris Traversal:

Follow the steps to implement the approach:

  • While the current node is not null, do the following:
    •    If the current node does not have a left child, then process the node and move to its right child.
    •   If the current node has a left child, then find its inorder predecessor (i.e., the rightmost node in its left subtree) and check if it is less than the current node’s value.
      • if the predecessor’s right child is null, then set it to point to the current node and move to the current node’s left child.
      •  If the predecessor’s right child is already pointing to the current node, then reset it to null (to restore the original binary tree structure), process the current node, and move to its right child.
    • Repeat steps b and c until the current node is null.
  • If the traversal completes without finding any violation of the BST property, then the binary tree is a valid BST

Below is the implementation of the above approach:

C++
// C++ code to implement the morris traversal approach
#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isValidBST(TreeNode* root) {
    TreeNode* curr = root;
    TreeNode* prev = NULL;
    
    while (curr != NULL) {
        if (curr->left == NULL) { // case 1: no left child
            // process the current node
            if (prev != NULL && prev->val >= curr->val)
                return false;
            prev = curr;
            curr = curr->right;
        }
        else { // case 2: has a left child
            // find the inorder predecessor
            TreeNode* pred = curr->left;
            while (pred->right != NULL && pred->right != curr)
                pred = pred->right;
            
            if (pred->right == NULL) { // make threaded link
                pred->right = curr;
                curr = curr->left;
            }
            else { // remove threaded link
                pred->right = NULL;
                // process the current node
                if (prev != NULL && prev->val >= curr->val)
                    return false;
                prev = curr;
                curr = curr->right;
            }
        }
    }
    
    return true; // binary tree is a valid BST
}
// Driver Code
int main() {
    // create the binary tree from the example
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    
    // check if the binary tree is a valid BST
    if (isValidBST(root))
        cout << "The binary tree is a valid BST." << endl;
    else
        cout << "The binary tree is not a valid BST." << endl;
    
    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot
Java
// Java code to implement the morris traversal approach

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x)
    {
        val = x;
        left = null;
        right = null;
    }
}

class GFG {
    public static boolean isValidBST(TreeNode root)
    {
        TreeNode curr = root;
        TreeNode prev = null;

        while (curr != null) {
            if (curr.left
                == null) { // case 1: no left child
                // process the current node
                if (prev != null && prev.val >= curr.val)
                    return false;
                prev = curr;
                curr = curr.right;
            }
            else { // case 2: has a left child
                // find the inorder predecessor
                TreeNode pred = curr.left;
                while (pred.right != null
                       && pred.right != curr)
                    pred = pred.right;

                if (pred.right
                    == null) { // make threaded link
                    pred.right = curr;
                    curr = curr.left;
                }
                else { // remove threaded link
                    pred.right = null;
                    // process the current node
                    if (prev != null
                        && prev.val >= curr.val)
                        return false;
                    prev = curr;
                    curr = curr.right;
                }
            }
        }

        return true; // binary tree is a valid BST
    }

    public static void main(String[] args)
    {
        // create the binary tree from the example
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        // check if the binary tree is a valid BST
        if (isValidBST(root))
            System.out.println(
                "The binary tree is a valid BST.");
        else
            System.out.println(
                "The binary tree is not a valid BST.");
    }
}
Python
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def isValidBST(root):
    curr = root
    prev = None
    
    while curr != None:
        if curr.left == None: # case 1: no left child
            # process the current node
            if prev != None and prev.val >= curr.val:
                return False
            prev = curr
            curr = curr.right
        else: # case 2: has a left child
            # find the inorder predecessor
            pred = curr.left
            while pred.right != None and pred.right != curr:
                pred = pred.right
            
            if pred.right == None: # make threaded link
                pred.right = curr
                curr = curr.left
            else: # remove threaded link
                pred.right = None
                # process the current node
                if prev != None and prev.val >= curr.val:
                    return False
                prev = curr
                curr = curr.right
    
    return True # binary tree is a valid BST

# Driver Code
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

# check if the binary tree is a valid BST
if isValidBST(root):
    print("The binary tree is a valid BST.")
else:
    print("The binary tree is not a valid BST.")
C#
using System;

// Definition for a binary tree node.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool IsValidBST(TreeNode root) {
        TreeNode curr = root;
        TreeNode prev = null;
        
        while (curr != null) {
            if (curr.left == null) { // case 1: no left child
                // process the current node
                if (prev != null && prev.val >= curr.val)
                    return false;
                prev = curr;
                curr = curr.right;
            }
            else { // case 2: has a left child
                // find the inorder predecessor
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr)
                    pred = pred.right;
                
                if (pred.right == null) { // make threaded link
                    pred.right = curr;
                    curr = curr.left;
                }
                else { // remove threaded link
                    pred.right = null;
                    // process the current node
                    if (prev != null && prev.val >= curr.val)
                        return false;
                    prev = curr;
                    curr = curr.right;
                }
            }
        }
        
        return true; // binary tree is a valid BST
    }
}

// Driver Code
public class Program {
    public static void Main() {
        // create the binary tree from the example
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        
        Solution solution = new Solution();
        
        // check if the binary tree is a valid BST
        if (solution.IsValidBST(root))
            Console.WriteLine("The binary tree is a valid BST.");
        else
            Console.WriteLine("The binary tree is not a valid BST.");
    }
}
Javascript
// Definition for a binary tree node.
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function isValidBST(root) {
    let curr = root;
    let prev = null;
    
    while (curr != null) {
        if (curr.left == null) { // case 1: no left child
            // process the current node
            if (prev != null && prev.val >= curr.val)
                return false;
            prev = curr;
            curr = curr.right;
        }
        else { // case 2: has a left child
            // find the inorder predecessor
            let pred = curr.left;
            while (pred.right != null && pred.right != curr)
                pred = pred.right;
            
            if (pred.right == null) { // make threaded link
                pred.right = curr;
                curr = curr.left;
            }
            else { // remove threaded link
                pred.right = null;
                // process the current node
                if (prev != null && prev.val >= curr.val)
                    return false;
                prev = curr;
                curr = curr.right;
            }
        }
    }
    
    return true; // binary tree is a valid BST
}

// Driver Code
let root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);

// check if the binary tree is a valid BST
if (isValidBST(root))
    console.log("The binary tree is a valid BST.");
else
    console.log("The binary tree is not a valid BST.");

Output
The binary tree is a valid BST.

Time Complexity: O(N), Where N is the number of nodes in the tree.
Auxiliary Space: O(1) , Because we are not using any addition data structure or recursive call stack.



Previous Article
Next Article

Similar Reads

Maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST
Given a binary tree, the task is to print the maximum sum of nodes of a sub-tree which is also a Binary Search Tree.Examples: Input : 7 / \ 12 2 / \ \ 11 13 5 / / \ 2 1 38 Output:44 BST rooted under node 5 has the maximum sum 5 / \ 1 38 Input: 5 / \ 9 2 / \ 6 3 / \ 8 7 Output: 8 Here each leaf node represents a binary search tree also a BST with su
12 min read
Check if a Binary Tree (not BST) has duplicate values
Check if a Binary Tree (not BST) has duplicate values To check if a binary tree has duplicate values, you can follow these steps: Create a set to store the values that have been encountered so far.Start a traversal of the binary tree. For each node, check if its value is in the set. If it is, return true to indicate that the tree contains duplicate
10 min read
Iterative approach to check if a Binary Tree is BST or not
Given a Binary Tree, the task is to check if the given binary tree is a Binary Search Tree or not. If found to be true, then print "YES". Otherwise, print "NO". Examples: Input: 9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8 Output: YES Explanation: Since the left subtree of each node of the tree consists of smaller valued nodes and the right subtree of each
9 min read
K'th Largest Element in BST when modification to BST is not allowed
Given a Binary Search Tree (BST) and a positive integer k, find the k'th largest element in the Binary Search Tree. For example, in the following BST, if k = 3, then output should be 14, and if k = 5, then output should be 10. We have discussed two methods in this post. The method 1 requires O(n) time. The method 2 takes O(h) time where h is height
15+ min read
Check whether a binary tree is a full binary tree or not | Iterative Approach
Given a binary tree containing n nodes. The problem is to check whether the given binary tree is a full binary tree or not. A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has only one child node. Examples: Input : 1 / \ 2 3 / \ 4 5 Outp
8 min read
Check whether a given binary tree is skewed binary tree or not?
Given a Binary Tree check whether it is skewed binary tree or not. A skewed tree is a tree where each node has only one child node or none. Examples: Input : 5 / 4 \ 3 / 2 Output : Yes Input : 5 / 4 \ 3 / \ 2 4 Output : No The idea is to check if a node has two children. If node has two children return false, else recursively compute whether subtre
13 min read
Check whether a binary tree is a full binary tree or not
A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has one child node. More information about full binary trees can be found here. For Example : Recommended PracticeFull binary treeTry It! To check whether a binary tree is a full binary tre
14 min read
Check if a Binary Tree is BST : Simple and Efficient Approach
Given a Binary Tree, the task is to check whether the given binary tree is Binary Search Tree or not.A binary search tree (BST) is a node-based binary tree data structure which has the following properties. The left subtree of a node contains only nodes with keys less than the node's key.The right subtree of a node contains only nodes with keys gre
6 min read
Check if the Binary Tree contains a balanced BST of size K
Given a Binary Tree and a positive integer K. The task is to check whether the Balanced BST of size K exists in a given Binary Tree or not. If it exists then print “Yes” else print “No”. Examples: Input: K = 4, Below is the given Tree: 15 / \ 10 26 / \ / \ 5 12 25 40 / / \ 20 35 50 \ 60 Output: Yes Explanation: Subtree of the given tree with size k
13 min read
Two nodes of a BST are swapped, correct the BST
Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST. Input: x = 20, y = 8 10 / \ 5 8 / \ 2 20Output: 10 / \ 5 20 / \ 2 8 Input: x = 10 y = 5 10 / \ 5 8 / \ 2 20Output: 5 / \ 10 20 / \ 2 8 Recommended ProblemFixing Two swapped nodes of a BSTSolve Problem Approach: The in-order traversal of a BST produces a sorted arr
15+ min read