Validate if Tree is BST in DSA C++ - Build from Scratch

Validate if Tree is BST

📖 Scenario: You are working with a simple binary tree structure in C++. You want to check if this tree follows the rules of a Binary Search Tree (BST). A BST is a tree where for every node, all nodes in the left subtree have smaller values, and all nodes in the right subtree have larger values.

🎯 Goal: Build a program that creates a binary tree, sets up a helper function to check BST rules, and then prints whether the tree is a valid BST or not.

📋 What You'll Learn

Create a binary tree with exactly 3 nodes with values 10, 5, and 15

Add a helper function to check if the tree is a BST using recursion

Use the helper function to determine if the tree is a BST

Print "BST" if the tree is valid, otherwise print "Not BST"

💡 Why This Matters

🌍 Real World

Checking if a tree is a BST is important in databases and search algorithms where data needs to be organized for fast lookup.

💼 Career

Understanding BST validation helps in roles involving data structures, algorithm design, and software engineering where tree data is common.

1

Create the binary tree nodes

Create a struct called Node with an int data and two pointers left and right. Then create three nodes named root, leftChild, and rightChild with values 10, 5, and 15 respectively. Connect leftChild as the left child of root and rightChild as the right child of root.

DSA C++

// Define Node struct and create root, leftChild, rightChild nodes
// Connect leftChild and rightChild to root
// Your code here

Hint

Define the Node struct first. Then create nodes using new Node{value, nullptr, nullptr}. Finally, link children to root.

2

Add helper function to check BST

Add a function called isBST that takes a Node* called node, and two int parameters min and max. This function returns true if the subtree rooted at node is a BST with all values strictly between min and max. If node is nullptr, return true. Otherwise, check if node->data is within the range, and recursively check left and right subtrees with updated ranges.

DSA C++

#include 
using namespace std;

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

// Add isBST function here

int main() {
    Node* root = new Node{10, nullptr, nullptr};
    Node* leftChild = new Node{5, nullptr, nullptr};
    Node* rightChild = new Node{15, nullptr, nullptr};
    root->left = leftChild;
    root->right = rightChild;
    // Your code here
    return 0;
}

Hint

Use recursion to check left subtree with max as current node's data, and right subtree with min as current node's data.

3

Use the helper function to check the tree

In main, call isBST with root, INT_MIN, and INT_MAX as arguments. Store the result in a boolean variable called result.

DSA C++

#include 
#include 
using namespace std;

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

bool isBST(Node* node, int min, int max) {
    if (node == nullptr) {
        return true;
    }
    if (node->data data >= max) {
        return false;
    }
    return isBST(node->left, min, node->data) && isBST(node->right, node->data, max);
}

int main() {
    Node* root = new Node{10, nullptr, nullptr};
    Node* leftChild = new Node{5, nullptr, nullptr};
    Node* rightChild = new Node{15, nullptr, nullptr};
    root->left = leftChild;
    root->right = rightChild;
    bool result = false;
    // Your code here
    return 0;
}

Hint

Call isBST with root, INT_MIN, and INT_MAX. Store the result in result.

4

Print if the tree is BST or not

Add a print statement that outputs "BST" if result is true, otherwise outputs "Not BST".

DSA C++

#include 
#include 
using namespace std;

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

bool isBST(Node* node, int min, int max) {
    if (node == nullptr) {
        return true;
    }
    if (node->data data >= max) {
        return false;
    }
    return isBST(node->left, min, node->data) && isBST(node->right, node->data, max);
}

int main() {
    Node* root = new Node{10, nullptr, nullptr};
    Node* leftChild = new Node{5, nullptr, nullptr};
    Node* rightChild = new Node{15, nullptr, nullptr};
    root->left = leftChild;
    root->right = rightChild;
    bool result = isBST(root, INT_MIN, INT_MAX);
    if (result) {
        // print BST
    } else {
        // print Not BST
    }
    return 0;
}

Hint

Use cout to print "BST" if result is true, else print "Not BST".