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.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. Every node has exactly two children.

B. For every node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger.

C. All leaf nodes are at the same depth.

D. The tree is perfectly balanced.

Solution

1. Step 1: Understand BST property

   A BST requires that for each node, values in the left subtree are smaller and values in the right subtree are larger.

2. Step 2: Compare other options

   Options B, C, and D describe other tree properties but not BST specifically.

3. Final Answer:

   For every node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger. -> Option B

4. Quick Check:

   BST property = left < node < right [OK]

Hint: Remember BST means left < node < right for all nodes [OK]

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Assuming leaf nodes must be at same depth

2. Which of the following C++ function signatures is correct to check if a binary tree is a BST using min and max limits?

easy

A. bool isBST(Node* root, int min, int max);

B. bool isBST(Node root, int min, int max);

C. bool isBST(Node* root, int min);

D. bool isBST(Node root);

Solution

1. Step 1: Check parameter types

   To check BST, we need a pointer to the root node and min/max limits to validate node values.

2. Step 2: Validate function signature

   bool isBST(Node* root, int min, int max); uses Node* root and both min and max parameters, which is correct for BST validation.

3. Final Answer:

   bool isBST(Node* root, int min, int max); -> Option A

4. Quick Check:

   Use pointer and min/max for BST check [OK]

Hint: Use pointer and min/max parameters for BST validation [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Missing max parameter
• Using incorrect parameter types

3. What will be the output of the following code snippet?

#include <iostream>
#include <climits>

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

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

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

int main() {
  Node n1 = {10, nullptr, nullptr};
  Node n2 = {5, nullptr, nullptr};
  Node n3 = {15, nullptr, nullptr};
  n1.left = &n2;
  n1.right = &n3;
  std::cout << (isBST(&n1) ? "Yes" : "No") << std::endl;
  return 0;
}

medium

A. Runtime error

B. No

C. Compilation error

D. Yes

Solution

1. Step 1: Analyze tree structure

   Root is 10, left child 5 < 10, right child 15 > 10, so BST property holds.

2. Step 2: Check BST validation function

   Function correctly checks node values within min and max limits recursively.

3. Final Answer:

   Yes -> Option D

4. Quick Check:

   Tree satisfies BST rules = Yes [OK]

Hint: Check left < root < right for all nodes [OK]

Common Mistakes:

• Confusing <= and < in comparisons
• Not passing correct min/max values
• Ignoring nullptr base case

4. Identify the bug in this BST validation code snippet:

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

medium

A. The function should not use recursion.

B. The base case should return false when root is nullptr.

C. The comparison should use <= min and >= max to exclude equal values.

D. The min and max parameters should be swapped in recursive calls.

Solution

1. Step 1: Check comparison operators

   BST requires strict inequality: node values must be greater than min and less than max, so use <= and >= to reject equal values.

2. Step 2: Validate base case and recursion

   Base case returning true for nullptr is correct; recursion is necessary; min and max parameters are correctly passed.

3. Final Answer:

   The comparison should use <= min and >= max to exclude equal values. -> Option C

4. Quick Check:

   Use strict inequalities to validate BST [OK]

Hint: Use <= and >= to reject duplicates in BST check [OK]

Common Mistakes:

• Allowing equal values breaks BST property
• Returning false on nullptr causes errors
• Swapping min and max in recursion

5. Given a binary tree where nodes can have duplicate values, how would you modify the BST validation function to allow duplicates only on the right subtree?

hard

A. Allow duplicates on right subtree by changing left subtree check to root->data < min and right subtree check to root->data >= max.

B. Change the left subtree check to root->data <= min and right subtree check to root->data > max.

C. Allow duplicates on left subtree by changing comparison to root->data <= min.

D. Disallow duplicates completely by using strict inequalities everywhere.

Solution

1. Step 1: Understand duplicate placement rule

   Duplicates allowed only on right subtree means left subtree nodes must be strictly less than root.

2. Step 2: Adjust comparison operators

   Left subtree check uses < min (strict), right subtree check uses >= max (allow equal or greater).

3. Final Answer:

   Allow duplicates on right subtree by changing left subtree check to root->data < min and right subtree check to root->data >= max. -> Option A

4. Quick Check:

   Duplicates only right = left < root, right >= root [OK]

Hint: Allow duplicates on right by using >= in right subtree check [OK]

Common Mistakes:

• Allowing duplicates on left subtree incorrectly
• Using <= on left subtree allowing duplicates there
• Not adjusting comparisons for duplicates