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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Validation Function

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

DSA C

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

#include <stdio.h>
#include <limits.h>

int isBSTUtil(Node* root, int min, int max) {
    if (root == NULL) return 1;
    if (root->data <= min || root->data >= max) return 0;
    return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}

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

int main() {
    Node n1 = {10, NULL, NULL};
    Node n2 = {5, NULL, NULL};
    Node n3 = {15, NULL, NULL};
    Node n4 = {3, NULL, NULL};
    Node n5 = {7, NULL, NULL};

    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;

    printf("%d\n", isBST(&n1));
    return 0;
}

A Compilation error

B 0

C 1

D Runtime error

💡 Hint

Check if all nodes satisfy the BST property with respect to min and max allowed values.

The tree is a valid BST because every node's value is within the allowed range defined by its ancestors.

The function returns 1 indicating true.

❓ Predict Output

intermediate

Output when Tree is Not a BST

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

DSA C

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

#include <stdio.h>
#include <limits.h>

int isBSTUtil(Node* root, int min, int max) {
    if (root == NULL) return 1;
    if (root->data <= min || root->data >= max) return 0;
    return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}

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

int main() {
    Node n1 = {10, NULL, NULL};
    Node n2 = {5, NULL, NULL};
    Node n3 = {8, NULL, NULL};
    Node n4 = {3, NULL, NULL};
    Node n5 = {12, NULL, NULL};

    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5; // Incorrect placement

    printf("%d\n", isBST(&n1));
    return 0;
}

A 1

B Runtime error

C Compilation error

D 0

💡 Hint

Look at the node with value 12 placed in the left subtree of 10.

The node with value 12 is in the left subtree of 10, which violates the BST property.

The function returns 0 indicating false.

🧠 Conceptual

advanced

Why Use Min and Max in BST Validation?

Why does the BST validation function pass min and max values during recursion?

A To keep track of the allowed value range for each node ensuring BST property.

B To count the number of nodes visited during traversal.

C To store the sum of all node values in the tree.

D To balance the tree after insertion.

💡 Hint

Think about how BST property restricts node values based on ancestors.

The min and max values define the valid range for each node's value to maintain BST ordering.

🔧 Debug

advanced

Identify the Bug in BST Validation Code

What is the bug in this BST validation code snippet?

DSA C

int isBSTUtil(Node* root, int min, int max) {
    if (root == NULL) return 1;
    if (root->data < min || root->data > max) return 0;
    return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}

A The function should not use recursion.

B The comparison should use <= and >= to correctly exclude equal values violating BST.

C The base case should return 0 instead of 1.

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

💡 Hint

Check how equality is handled in BST property.

BST does not allow duplicate values on the same side, so <= and >= are needed to reject equal values.

🚀 Application

expert

Number of Nodes in Valid BST Subtree

Given a binary tree, which option correctly returns the size of the largest valid BST subtree inside it?

DSA C

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

// Assume helper functions and structs are defined

int largestBSTSubtree(Node* root) {
    // Implementation omitted
    return 0;
}

int main() {
    Node n1 = {10, NULL, NULL};
    Node n2 = {5, NULL, NULL};
    Node n3 = {15, NULL, NULL};
    Node n4 = {1, NULL, NULL};
    Node n5 = {8, NULL, NULL};
    Node n6 = {7, NULL, NULL};

    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.left = &n6;

    printf("%d\n", largestBSTSubtree(&n1));
    return 0;
}

A 4

B 3

C 5

D 6

💡 Hint

Identify the largest subtree that satisfies BST properties.

The largest BST subtree includes nodes 5, 1, 8, and 7 is invalid because 7 is in right subtree of 15 but less than 15.

The largest valid BST subtree is rooted at node 5 with nodes 5, 1, and 8.

Practice

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

easy

A. Each node has exactly two children

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

C. All nodes have unique values

D. The tree is perfectly balanced

Solution

1. Step 1: Understand BST property

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

2. Step 2: Compare options with BST definition

   For each node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger matches the BST property exactly, while others describe different tree properties.

3. Final Answer:

   For each 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 = For each node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger [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 unique values define BST

2. Which of the following C function signatures is correct to check if a binary tree is a BST?

easy

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

B. void isBST(struct Node* root);

C. int isBST(struct Node* root);

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

Solution

1. Step 1: Identify typical BST check function parameters

   Checking BST usually requires passing current node and min/max limits to validate subtree values.

2. Step 2: Match function signatures

   int isBST(struct Node* root, int min, int max); uses int return type and min/max parameters, which is common in C. bool isBST(struct Node* root, int min, int max); uses bool which is not standard C. Options B and C lack min/max parameters.

3. Final Answer:

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

4. Quick Check:

   BST check needs min/max limits and int return [OK]

Hint: Use min/max limits in function parameters for BST check [OK]

Common Mistakes:

• Omitting min/max parameters
• Using bool type in plain C
• Using void return type for boolean check

3. Given the following tree structure and code snippet, what will be the output?

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

int isBSTUtil(struct Node* node, int min, int max) {
  if (node == NULL) return 1;
  if (node->data <= min || node->data >= max) return 0;
  return isBSTUtil(node->left, min, node->data) && isBSTUtil(node->right, node->data, max);
}

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

// Tree:
//      10
//     /  \
//    5   15
//       /  \
//      6   20

int main() {
  struct Node n1 = {10, NULL, NULL};
  struct Node n2 = {5, NULL, NULL};
  struct Node n3 = {15, NULL, NULL};
  struct Node n4 = {6, NULL, NULL};
  struct Node n5 = {20, NULL, NULL};
  n1.left = &n2; n1.right = &n3;
  n3.left = &n4; n3.right = &n5;
  printf("%d\n", isBST(&n1));
  return 0;
}

medium

A. 1

B. Undefined behavior

C. Compilation error

D. 0

Solution

1. Step 1: Analyze tree structure and BST property

   The node with value 6 is in the right subtree of 10 but less than 10, violating BST property.

2. Step 2: Trace isBSTUtil calls

   When checking node 6, min=15 and max=INT_MAX, 6 <= 15 fails the condition, so returns 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Node 6 violates BST rules, so output = 0 [OK]

Hint: Check if any node violates min/max limits during recursion [OK]

Common Mistakes:

• Ignoring subtree min/max constraints
• Assuming all left < root and right > root only locally
• Not tracing recursive calls carefully

4. Identify the bug in this BST validation function and select the fix:

int isBST(struct Node* root) {
  if (root == NULL) return 1;
  if (root->left != NULL && root->left->data >= root->data) return 0;
  if (root->right != NULL && root->right->data <= root->data) return 0;
  if (!isBST(root->left) || !isBST(root->right)) return 0;
  return 1;
}

medium

A. Add min and max parameters to check entire subtree ranges

B. Change >= to > and <= to < in comparisons

C. Remove recursive calls to isBST

D. Return 0 if root is NULL

Solution

1. Step 1: Understand current checks

   The function only compares immediate children with root, missing deeper subtree violations.

2. Step 2: Explain why min/max parameters are needed

   To validate BST fully, we must ensure all nodes in left subtree < root and right subtree > root using min/max limits recursively.

3. Final Answer:

   Add min and max parameters to check entire subtree ranges -> Option A

4. Quick Check:

   Min/max limits fix subtree validation [OK]

Hint: Use min/max limits to validate entire subtree, not just immediate children [OK]

Common Mistakes:

• Checking only immediate children
• Ignoring subtree value ranges
• Misusing comparison operators

5. You want to validate if a binary tree is a BST but the tree may contain duplicate values allowed only on the right subtree. How would you modify the BST validation logic in C?

hard

A. Use strict > and < comparisons for both subtrees

B. Allow duplicates only on left subtree by changing conditions

C. Change the condition to allow node->data >= min and < max for right subtree

D. Ignore duplicates and check only structure

Solution

1. Step 1: Understand duplicate allowance rule

   Duplicates allowed only on right subtree means left subtree nodes must be strictly less, right subtree nodes can be equal or greater.

2. Step 2: Modify min/max checks accordingly

   For left subtree, use node->data > min and < root->data; for right subtree, allow node->data >= root->data and < max.

3. Final Answer:

   Change the condition to allow node->data >= min and < max for right subtree -> Option C

4. Quick Check:

   Allow duplicates on right by using >= on right subtree [OK]

Hint: Allow duplicates on right by using >= comparison there [OK]

Common Mistakes:

• Allowing duplicates on left subtree incorrectly
• Using strict inequalities everywhere
• Ignoring duplicate rules