Validate if Tree is BST in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Validation on a Simple Tree

What is the output of the following C++ code that checks if a binary tree is a BST?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isBSTUtil(Node* root, int minVal, int maxVal) {
    if (!root) return true;
    if (root->val <= minVal || root->val >= maxVal) return false;
    return isBSTUtil(root->left, minVal, root->val) && isBSTUtil(root->right, root->val, maxVal);
}

bool isBST(Node* root) {
    return isBSTUtil(root, INT_MIN, INT_MAX);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(2);
    root->left->right = new Node(7);
    root->right->left = new Node(12);
    root->right->right = new Node(20);
    
    if (isBST(root))
        std::cout << "true" << std::endl;
    else
        std::cout << "false" << std::endl;
    return 0;
}

A true

B false

C Compilation error

D Runtime error

💡 Hint

Check if all nodes follow the BST property: left < root < right.

The tree is a valid BST because all left children are less than their parent nodes and all right children are greater. The code correctly checks this using min and max bounds.

❓ Predict Output

intermediate

Output when Tree Violates BST Property

What is the output of this C++ code that checks if a binary tree is a BST, where one node violates the BST property?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isBSTUtil(Node* root, int minVal, int maxVal) {
    if (!root) return true;
    if (root->val <= minVal || root->val >= maxVal) return false;
    return isBSTUtil(root->left, minVal, root->val) && isBSTUtil(root->right, root->val, maxVal);
}

bool isBST(Node* root) {
    return isBSTUtil(root, INT_MIN, INT_MAX);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(8); // Violates BST property: should be > 10
    root->left->left = new Node(2);
    root->left->right = new Node(7);
    
    if (isBST(root))
        std::cout << "true" << std::endl;
    else
        std::cout << "false" << std::endl;
    return 0;
}

A Compilation error

B true

C false

D Runtime error

💡 Hint

Check the right child of root; it must be greater than root's value.

The right child of the root has value 8, which is less than 10, violating the BST property. Hence, the function returns false.

🧠 Conceptual

advanced

Why Use Min and Max Bounds in BST Validation?

Why does the BST validation function pass minimum and maximum values down the recursion?

A To count the number of nodes in the tree.

B To ensure each node's value is within the valid range defined by its ancestors.

C To balance the tree during traversal.

D To store the path from root to current node.

💡 Hint

Think about how BST property depends on ancestor nodes, not just immediate parent.

Passing min and max bounds ensures that each node respects the BST property relative to all its ancestors, not just its parent.

🔧 Debug

advanced

Identify the Bug in BST Validation Code

What is the bug in this BST validation code snippet?

DSA C++

bool isBSTUtil(Node* root, int minVal, int maxVal) {
    if (!root) return true;
    if (root->val < minVal || root->val > maxVal) return false;
    return isBSTUtil(root->left, minVal, root->val) && isBSTUtil(root->right, root->val, maxVal);
}

A The comparison should use <= and >= to handle equal values correctly.

B The function should not use recursion.

C The base case should return false instead of true.

D The minVal and maxVal parameters are not needed.

💡 Hint

Consider if equal values are allowed in BST and how the code handles them.

Using < and > allows equal values to pass, which can violate BST rules if duplicates are not allowed on either side.

🚀 Application

expert

Number of Nodes in a Valid BST After Insertions

Given an initially empty BST, the following values are inserted in order: 20, 10, 30, 25, 40, 22. After all insertions, how many nodes does the BST contain?

A 4

B 5

C 7

D 6

💡 Hint

Count each inserted value as one node; no duplicates are inserted.

Each insertion adds one node since all values are unique. Total nodes = 6.