Validate if Tree is BST in DSA C - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check left subtree

↓

Is left subtree BST?

↓

Check current node value

↓

Check right subtree

↓

Is right subtree BST?

↓

Return True

We start at the root, recursively check left subtree, then current node value, then right subtree to confirm BST property.

Execution Sample

DSA C

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

This code checks if a binary tree is a BST by ensuring each node's value is within valid min and max bounds.

Execution Table

Step	Operation	Node Visited	Min Bound	Max Bound	Result	Tree State
1	Start at root	10	-∞	+∞	Check left subtree	10 / \ 5 15
2	Check left subtree	5	-∞	10	Check left subtree	10 / \ 5 15
3	Check left subtree	3	-∞	5	Check left subtree	10 / \ 5 15 / 3
4	Check left subtree	NULL	-∞	3	True (leaf)	10 / \ 5 15 / 3
5	Check right subtree	NULL	3	5	True (leaf)	10 / \ 5 15 / 3
6	Node 3 valid?	3	-∞	5	True	10 / \ 5 15 / 3
7	Check right subtree	7	5	10	Check left subtree	10 / \ 5 15 / 3 7
8	Check left subtree	NULL	5	7	True (leaf)	10 / \ 5 15 / 3 7
9	Check right subtree	NULL	7	10	True (leaf)	10 / \ 5 15 / 3 7
10	Node 7 valid?	7	5	10	True	10 / \ 5 15 / 3 7
11	Node 5 valid?	5	-∞	10	True	10 / \ 5 15 / 3 7
12	Check right subtree	15	10	+∞	Check left subtree	10 / \ 5 15 / 3 7 NULL
13	Check left subtree	NULL	10	15	True (leaf)	10 / \ 5 15 / 3 7 NULL
14	Check right subtree	20	15	+∞	Check left subtree	10 / \ 5 15 / 3 7 NULL 20
15	Check left subtree	NULL	15	20	True (leaf)	10 / \ 5 15 / 3 7 NULL 20
16	Check right subtree	NULL	20	+∞	True (leaf)	10 / \ 5 15 / 3 7 NULL 20
17	Node 20 valid?	20	15	+∞	True	10 / \ 5 15 / 3 7 NULL 20
18	Node 15 valid?	15	10	+∞	True	10 / \ 5 15 / 3 7 NULL 20
19	Node 10 valid?	10	-∞	+∞	True	10 / \ 5 15 / 3 7 NULL 20
20	All checks passed	N/A	N/A	N/A	Return True	10 / \ 5 15 / 3 7 NULL 20

💡 All nodes satisfy BST property, recursion ends returning True

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 11	After Step 18	Final
node	10	5	7	5	15	10
min	-∞	-∞	5	-∞	10	-∞
max	+∞	10	10	10	+∞	+∞
Result	N/A	Check left subtree	Check right subtree	Node 5 valid	Node 15 valid	True

Key Moments - 3 Insights

Why do we check if node->data <= min or node->data >= max?

Because each node must be strictly greater than min and less than max to maintain BST order, as shown in steps 3, 7, and 12 in the execution_table.

Why do we pass node->data as new max for left subtree and as new min for right subtree?

This keeps track of valid value ranges for subtrees, ensuring no violations occur deeper in the tree, as seen in steps 2 and 12 where bounds update.

What happens when node is NULL?

It means we've reached a leaf's child, so we return True (leaf is valid), as shown in steps 4, 5, 8, 9, 13, 15, and 16.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the min and max bounds for node 7?

A min = 5, max = 10

B min = -∞, max = 5

C min = 7, max = 10

D min = 3, max = 7

💡 Hint

Check columns 'Min Bound' and 'Max Bound' at step 7 in execution_table

At which step does the recursion confirm node 20 is valid?

A Step 14

B Step 17

C Step 16

D Step 18

💡 Hint

Look for 'Node 20 valid?' in the 'Operation' column in execution_table

If node 7 had value 11 instead, which step's result would change to False?

A Step 7

B Step 18

C Step 10

D Step 19

💡 Hint

Check step 10 where node 7's validity is evaluated against min=5 and max=10

Concept Snapshot

Validate if Tree is BST:
- Use recursion with min and max bounds
- For each node, check if value is > min and < max
- Recurse left with max = node's value
- Recurse right with min = node's value
- Return True if all nodes satisfy bounds
- Return False immediately if violation found

Full Transcript

To check if a binary tree is a BST, we start at the root and recursively verify each node's value lies within allowed min and max bounds. For the left subtree, the max bound is the current node's value; for the right subtree, the min bound is the current node's value. If any node violates these bounds, we return False. If we reach a null node, we return True as leaf nodes are valid. This process continues until all nodes are checked. The execution table shows step-by-step traversal and validation of nodes 10, 5, 3, 7, 15, and 20 with their respective bounds. The variable tracker records the changing min and max bounds and current node during recursion. Key moments clarify why bounds are checked and updated. The visual quiz tests understanding of bounds and validation steps.

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