Validate Binary Search Tree: Check if BST or not? (Java & C++)

If you have studied DSA in your college, then you know what trees are, and how bad the questions related to them can be. The different types of trees in Data Structures can confuse anybody!

So, in today's tech blog we are going to discuss Binary Search Trees, and how you can validate that a particularly given tree is a BST. Get ready for examples, of different methods for solving the same question along with their implementation in C++ and Java. Let's get started, folks!

What is a BST?

A Binary Search Tree is a tree data structure that is based on nodes. It has the following properties:

• The Left sub-tree of a node contains nodes with keys less than the node's key.
• The Right Subtree of the node contains nodes with keys greater than the node's key. 
• Both left and right subtrees should individually be Binary Search Trees. 
• Each node(value in the tree) should have a distinct key.

If a given tree satisfies the above properties, it is a BST. Still confused? Look at the given illustration:

Validate BST Problem Statement

Here is the problem statement: "You are given a tree data structure. You need to check whether it is a BST or not. For checking this thing, you need to check the above 4 properties of the tree individually."

In short, we have to validate a binary search tree.

Example

Look at the given image to see what the problem is.

03 Methods to Validate Binary Search Tree

Although the question is the same, we still have like 3 methods for you to solve this! 

Method 01) Naive Approach

The following steps need to be followed for this approach:

1. Check whether the node is single or not. If yes, return True. 
2. Traverse every node in the left subtree, and check whether each value is less than the root's value. 
3. Traverse every node in the right subtree, and check whether each value is bigger than the root's value. 
4. If a node in the left subtree is found to have a bigger value than the root, Return False. 
5. If a node in the right subtree is found to have a smaller value than the root, Return False. 
6. Keep checking whether both the left and right subtrees of the root are also BST. 
7. If yes, return True. 

Method 02) Using Upper & Lower Limits

For implementing this method, follow the given steps:

1. If currentNode == NULL, return True. 
2. If LowerLimit is not equal to NULL and the value at CurrentNode <= LowerLimit, return False. 
3. If UpperLimit is not equal to NULL and the value at CurrentNode >= UpperLimit, return False. 
4. Keep checking whether the left subtree of CurrentNode is BST or not, along with the value of CurrentNode as UpperLimit and LowerLimit as the lower limit. 
5. If the left subtree is not BST, return False. 
6. Keep checking whether the right subtree of CurrentNode is BST or not, along with the value of CurrentNode as LowerLimit and UpperLimit as the upper limit. 
7. If the right subtree is not BST, return False. Else, return True. 

Method 03) Using Inorder Traversal

How can an Inorder Traversal validate a BST? Well, this is because if on traversing a tree in an inorder fashion, it gives a Sorted array of tree values, then it is a Binary Search Tree. Let's take a deeper look at this!

If the in-order traversal of a tree returns a sorted array of elements, then it is quite obvious that the right and left subtrees of the tree will also give sorted elements. Why? This is because the Inorder Traversal of a tree always traverses the Left Subtree, then the root, and later the Right Subtree. Now, this means that every node value in Left Subtree should be smaller than the root's value, and that also means that every node value in the right subtree must be greater than the root's value. 

Now, this in-order traversal method can be improved by observing that we don't have to store every node value. We can just check if the previous element in the tree traversal is less than the current element. 

Code Implementation in C++

Here is the C++ code to validate BST:

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

struct node {
	int data;
	struct node* left;
	struct node* right;
};

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));
}

int isBST(struct node* node)
{
	if (node == NULL)
		return 1;

	if (node->left != NULL
		&& maxValue(node->left) > node->data)
		return 0;
	if (node->right != NULL
		&& minValue(node->right) < node->data)
		return 0;

	if (!isBST(node->left) || !isBST(node->right))
		return 0;
	return 1;
}


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);
	if (isBST(root))
		printf("Is BST");
	else
		printf("Not a BST");

	return 0;
}

Code Implementation in Java

Here is the Java code to validate BST:

import java.io.*;

class Solution {
static class node {
	int data;
	node left, right;
}

static node newNode(int info)
{
	node Node = new node();
	Node.info = info;
	Node.left = Node.right = null;
	return Node;
}

static int Value(node Node)
{
	if (Node == null) {
	return Integer.MIN_VALUE;
	}
	int value = Node.data;
	int leftMax = Value(Node.left);
	int rightMax = Value(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));
}

static int BST(node Node)
{
	if (Node == null) {
	return 1;
	}
	
	if (Node.left != null
		&& maxValue(Node.left) > Node.data) {
	return 0;
	}
	
	if (Node.right != null
		&& minValue(Node.right) < Node.data) {
	return 0;
	}
	
	if (isBST(Node.left) != 1
		|| isBST(Node.right) != 1) {
	return 0;
	}
	
	return 1;
}

public static void main(String[] args)
{
	node root = newNode(4);
	root.left = newNode(2);
	root.right = newNode(5);
	root.left.left = newNode(1);
	root.left.right = newNode(3);

	if (BST(root) == 1) {
	System.out.print("Is BST");
	}
	else {
	System.out.print("Not a BST");
	}
}
}

Output:

Is BST

Conclusion

So, in this tech blog, we came up with 3 different solutions to validate a Binary Search Tree. Although each solution is good on its own, the last one, that is, the inorder traversal of trees is the best to use in practice. For more such tech blogs on complex topics, you can always rely on FavTutor!