How to Validate Binary Search Tree Using Java and C++ Code

Do you want to know how to validate binary search tree? If yes, then check out this blog to understand the best ways to validate binary search tree

Every programmer understands how important Data Structures and Algorithms are for them. But some DSA concepts can be outrageously complex to understand, Trees being a classic example for that.

They are one of the most foundational concepts for advanced Data Structures and Algorithms like Graphs, Breadth-First Search and Depth-First-Search etc.

In this blog, we will learn about how to validate binary search tree. But first, let’s understand what is a binary search tree.

What is a Binary Search Tree (or BST) ?

A binary tree is a data structure made of nodes connected to each other, which can be represented as a tree (note that no actual tree shape forms in the memory.

It is just to understand the working of tree in a better manner) with at most two nodes connected to a single node (which constitute the left subtree and right subtree respectively).

A binary tree data structure has the following components for each node:

• Key : The data value of the node
• Left: A reference to the left child node
• Right: A reference to the right child node

A Binary Search Tree is a special type of binary tree in which satisfies the following conditions :

• The left sub-tree must contain all keys which are less than the current node’s key value
• The right sub-tree must contain all keys which are greater than the current node’s key value
• No key value should be repeated in the entire BST
• Both the left sub-tree

What do we mean by Validating a BST ?

The problem that we are dealing with here is to tell whether a given binary tree is BST or not. 

If the given tree is a BST then we need to return true, otherwise we should return false.

In order to do that, we need to check the conditions of the Binary Search Tree,  discussed earlier in this article, for the given tree. 

There are several methods to validate the given tree. Let us discuss them one by one.

Validate Binary Search Tree

Brute Force Approach

The brute force approach (in general) is an approach aimed at just solving the problem and getting the desired results. It does not cater to the scope for optimization and therefore, not a preferred approach for practical purposes.

1. Check if the root has no children. If yes, return true
2. Traverse the left sub-tree. If for any node, the value of the node is greater than the root, return false.
3. Traverse the right sub-tree. If for any node, the value of the node is less than the root, return false.
4. Repeat the above steps for each node in the left and right sub-tree respectively.

Time Complexity : O(n²)

Auxiliary Space Used: O(lg(n))

Using Upper and Lower Limit Values

In this method three variable, the currentNode, upperLimit, lowerLimit are declared as:

• currentNode = root
• upperLimit = NULL
• lowerLimit = NULL

Then we follow the following steps:

• If the currentNode = null, return true
• If lowerLimit is not null and currentNode <= lowerLimit , return false
• If upperLimit is not null and currentNode >= upperLimit , return false
• Repeat the above steps for the left sub-tree and check whether it is a BST or not having currentNode as upperLimit and lowerLimit as lowerLimit. If the left sub-tree is not a BST, return false
• Keep checking that the right sub-tree is BST or not having the currentNode as lowerLimit and upperLimit as upperLimit.
• If the right sub-tree is not a BST, return false, else return true

Time Complexity : O(n)

Auxiliary Space Used: O(1)

Using In-order Traversal

This method uses in-order traversal of the tree. It works because the level order search results of a BST result in a sorted order of the tree elements.

When we are performing the in-order traversal, the control first goes to the left subtree, then the current node, and then the right subtree.

If we perform this in a Binary Search Tree, we know that the three elements must be in an increasing order, because any value in the left subtree will be smaller than the current node and any value in the right subtree will be greater than the current node.

Thus, we only need to perform in-order traversal on the given tree and check if the previous element in the traversal is less than the current element. If not, we return false. If false is not returned for the entire traversal, we return true.

Time Complexity : O(n)

Auxiliary Space Used: O(lg(n))

You May Also Like

9+ Java Swing Vs JavaFX Comparisons — Which Is Better?

Code Implementation

Now, we will discuss how to implement the above logic into both C++ and Java. For this, we will be using the following tree as input.

Java Implementation

import java.io.*;

class solution {

static class node {

    int val;

    node left, right;

}

static node newNode(int info)

{

    node Node = new node();

    Node.val = info;

    Node.left = Node.right = null;

    return Node;

}

static int maxVal(node Node)

{

    if (Node == null) {

    return Integer.MIN_VALUE;

    }

    int value = Node.val;

    int leftMax = maxVal(Node.left);

    int rightMax = maxVal(Node.right);

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

}

static int minVal(node Node)

{

    if (Node == null) {

    return Integer.MAX_VALUE;

    }

    int value = Node.val;

    int leftMax = minVal(Node.left);

    int rightMax = minVal(Node.right);

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

}

static int validateBST(node Node)

{

    if (Node == null) {

    return 1;

    }

    if (Node.left != null

        && maxVal(Node.left) > Node.val) {

    return 0;

    }

    if (Node.right != null

        && minVal(Node.right) < Node.val) {

    return 0;

    }

    if (validateBST(Node.left) != 1

        || validateBST(Node.right) != 1) {

    return 0;

    }

    return 1;

}

public static void main(String[] args)

{

    node root = newNode(10);

    root.left = newNode(7);

    root.right = newNode(13);

    root.left.left = newNode(5);

    root.left.right = newNode(9);

    root.right.left = newNode(11);

    root.right.right = newNode(15);

    if (validateBST(root) == 1) {

    System.out.print("Given tree is a BST");

    }

    else {

    System.out.print("Given tree is not a BST");

    }

}

}

Output:

Given tree is a BST

C++ Implementation

This is the implementation of the above method in C++ to check if the given tree is a BST or not.

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

Output:

Given tree is a BST

Conclusion

In this article, we discussed about how to validate binary search tree. We also discussed various ways in which we can check if a binary tree is a BST or not and also how to implement those logics in C++ and Java.

From the above mentioned methods, the in-order  traversal method is the most practically used (and preferred ) method for BST validation although other methods may also work according to the nature of the program. If you think we have missed anything about validate binary search tree then comment down below.