DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

EXPERIMENT - 8

Name: Shashank Shukla UID: 21BCS5770

Branch: AIT-CSE (AIML) Section/Group: 21AML-4B
Semester: 6th Date of Performance: 30-03-2024
Subject Name: Technical Training Subject Code: 21CSP-382

Aim: Write a program in C++ using recursion function to check if the binary tree is the binary search tree.

Requirements: Online compiler

Theory: The program is designed to determine whether a given binary tree is a binary search tree
(BST). A binary search tree is a binary tree in which the value of each node in the left subtree is less
than the node's value, and the value of each node in the right subtree is greater than the node's value.
To achieve this, the program employs a recursive approach. The `isBSTUtil` function is a recursive
function that checks each node in the binary tree to ensure it satisfies the BST property. It traverses
the tree recursively, updating the valid range of values for each node based on its position in the tree.
The function returns true if the tree is empty or if all nodes in the tree satisfy the BST property;
otherwise, it returns false. The main function interacts with the user to create a binary tree based on
their input values and then calls the `isBST` function to determine whether the entered binary tree is
a binary search tree. This program demonstrates the use of recursion in checking the properties of a
binary tree, specifically whether it meets the criteria of being a binary search tree. \

Algorithm:

1. Define the TreeNode structure: Define a structure to represent each node of the binary tree, including its
value, left child, and right child.

2. Define the isBSTUtil Function: Define a recursive function `isBSTUtil` that takes a TreeNode pointer, along with
minimum and maximum integer values representing the valid range for the node's value. This function
recursively checks whether the given binary tree satisfies the properties of a binary search tree (BST). It
returns true if the tree is empty or if all nodes in the tree satisfy the BST property; otherwise, it returns false.

Base Case:

- If the node is NULL, return true (an empty tree is a BST).

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

- If the node's value is outside the valid range, return false.

Recursive Steps:

- Recursively call `isBSTUtil` for the left subtree, updating the maximum value to be one less than the
current node's value.

- Recursively call `isBSTUtil` for the right subtree, updating the minimum value to be one more than the
current node's value.

3. Define the isBST Function: Define a function `isBST` that serves as a wrapper function for `isBSTUtil`. It takes a
TreeNode pointer representing the root of the binary tree and calls `isBSTUtil` with initial minimum and
maximum values as negative infinity and positive infinity, respectively.

4. Define the createBinaryTree Function (Optional): Optionally, define a function to allow user input for creating
a binary tree. This function prompts the user to enter values for each node and constructs the binary tree
accordingly.

- The function takes input for the root value and then iteratively prompts for parent-child node pairs
until the user decides not to enter more nodes.

- It creates the binary tree based on the user's input.

5. Main Function: In the main function:

- Call the `createBinaryTree` function to create the binary tree (optional if user input is required).

- Call the `isBST` function to determine whether the entered binary tree is a binary search tree.

- Print appropriate messages based on the result.

Code Implementation:

#include <iostream> #include

<climits> using namespace

std; struct TreeNode {

int val;
TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

bool isBSTUtil(TreeNode* node, int minValue, int maxValue) { if

(node == NULL)

return true;

if (node->val < minValue || node->val > maxValue)

return false;

return isBSTUtil(node->left, minValue, node->val - 1) &&

isBSTUtil(node->right, node->val + 1, maxValue);

bool isBST(TreeNode* root) { return isBSTUtil(root,

INT_MIN, INT_MAX);

TreeNode* createBinaryTree() {

int val;

cout << "Enter root value: ";

cin >> val;

TreeNode* root = new TreeNode(val);

char choice; do { int

parentVal, childVal;
cout << "Enter parent value: ";

cin >> parentVal; cout << "Enter

child value: "; cin >> childVal;

TreeNode* parent = NULL;

parent = root;

TreeNode* child = new TreeNode(childVal);

if (parent->left == NULL)

parent->left = child;

else
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

parent->right = child;

cout << "Do you want to enter more nodes? (y/n): ";

cin >> choice;

} while (choice == 'y' || choice == 'Y'); return

root;

int main() {

TreeNode* root = createBinaryTree(); if

(isBST(root)) cout << "The binary tree is a binary

search tree." << endl;

else

cout << "The binary tree is not a binary search tree." << endl; return

0;

Output:

Result: Successfully implemented the program.

Learning Outcomes:

1. Learnt about binary tree in DSA.

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

2. Learnt about using recursion for identifying whether the tree is a binary search tree.

3. Learnt to solve the problem in less time.