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 check recursively if left subtree is BST, then current node value fits BST rules, then right subtree is BST.

Execution Sample

DSA C++

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

This code checks if a binary tree is a BST by verifying node values lie within valid min and max ranges.

Execution Table

Step	Operation	Node Visited	Min Allowed	Max Allowed	Check Result	Return Value	Tree State
1	Start at root	10	-∞	+∞	10 > -∞ and 10 < +∞	Pending	[10]
2	Check left subtree	5	-∞	10	5 > -∞ and 5 < 10	Pending	[10, 5]
3	Check left subtree of 5	2	-∞	5	2 > -∞ and 2 < 5	Pending	[10, 5, 2]
4	Check left subtree of 2	null	-∞	2	null node	True	[10, 5, 2]
5	Check right subtree of 2	null	2	5	null node	True	[10, 5, 2]
6	Return from node 2	2	-∞	5	Both subtrees True	True	[10, 5, 2]
7	Check right subtree of 5	7	5	10	7 > 5 and 7 < 10	Pending	[10, 5, 2, 7]
8	Check left subtree of 7	null	5	7	null node	True	[10, 5, 2, 7]
9	Check right subtree of 7	null	7	10	null node	True	[10, 5, 2, 7]
10	Return from node 7	7	5	10	Both subtrees True	True	[10, 5, 2, 7]
11	Return from node 5	5	-∞	10	Both subtrees True	True	[10, 5, 2, 7]
12	Check right subtree	15	10	+∞	15 > 10 and 15 < +∞	Pending	[10, 5, 2, 7, 15]
13	Check left subtree of 15	12	10	15	12 > 10 and 12 < 15	Pending	[10, 5, 2, 7, 15, 12]
14	Check left subtree of 12	null	10	12	null node	True	[10, 5, 2, 7, 15, 12]
15	Check right subtree of 12	null	12	15	null node	True	[10, 5, 2, 7, 15, 12]
16	Return from node 12	12	10	15	Both subtrees True	True	[10, 5, 2, 7, 15, 12]
17	Check right subtree of 15	20	15	+∞	20 > 15 and 20 < +∞	Pending	[10, 5, 2, 7, 15, 12, 20]
18	Check left subtree of 20	null	15	20	null node	True	[10, 5, 2, 7, 15, 12, 20]
19	Check right subtree of 20	null	20	+∞	null node	True	[10, 5, 2, 7, 15, 12, 20]
20	Return from node 20	20	15	+∞	Both subtrees True	True	[10, 5, 2, 7, 15, 12, 20]
21	Return from node 15	15	10	+∞	Both subtrees True	True	[10, 5, 2, 7, 15, 12, 20]
22	Return from root 10	10	-∞	+∞	Both subtrees True	True	[10, 5, 2, 7, 15, 12, 20]

💡 All nodes satisfy BST conditions, recursion ends with True

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 11	After Step 21	Final
node	10 (root)	5 (left child)	5 (left child)	10 (root)	15 (right child)	10 (root)
min	-∞	-∞	-∞	-∞	10	-∞
max	+∞	10	10	10	+∞	+∞
return value	Pending	Pending	True	True	True	True

Key Moments - 3 Insights

Why do we pass min and max values when checking each node?

The min and max track the allowed value range for each node. See execution_table steps 2, 12 where min and max change to keep BST rules.

What happens when we reach a null node?

Null nodes mean leaf ends and are considered valid BST parts. See steps 4, 5, 8 where null nodes return True.

Why do we check node->val <= min or >= max instead of just equality?

BST requires strict less or greater, no duplicates allowed. See step 3 where node value must be strictly between min and max.

Visual Quiz - 3 Questions

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

A min = 5, max = 10

B min = -∞, max = 10

C min = 2, max = 7

D min = 7, max = 10

💡 Hint

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

At which step does the recursion confirm the left subtree of root is a BST?

A Step 6

B Step 11

C Step 21

D Step 22

💡 Hint

Look for 'Return from node 5' with return value True in execution_table

If node 12 had value 9 instead, which step would fail the BST check?

A Step 16

B Step 12

C Step 13

D Step 17

💡 Hint

Check step 13 where node 12 is checked against min=10 and max=15

Concept Snapshot

Validate BST by recursion:
- Start at root with min=-∞, max=+∞
- Check node value in (min, max)
- Recurse left with max=node.val
- Recurse right with min=node.val
- Null nodes return True
- If any check fails, return False

Full Transcript

To check if a binary tree is a BST, we start at the root node and verify if its value lies within allowed minimum and maximum bounds. Initially, these bounds are negative and positive infinity. We then recursively check the left subtree, updating the maximum bound to the current node's value, and the right subtree, updating the minimum bound to the current node's value. If a node is null, it is considered valid. If any node violates the bounds, the tree is not a BST. The execution table shows each step visiting nodes, checking values against bounds, and returning True or False accordingly. The variable tracker follows the current node and bounds during recursion. Key moments clarify why bounds are needed, how null nodes are handled, and why strict inequalities are used. The visual quiz tests understanding of bounds at specific steps and failure points. This method ensures the entire tree satisfies BST properties.

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