Validate if Tree is BST in DSA C# - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check left subtree values < current node?

↓

Recursively validate left subtree

↓

Check right subtree values > current node?

↓

Recursively validate right subtree

↓

If all checks pass, return True

↓

Else return False

Start from the root, recursively check if left subtree nodes are less and right subtree nodes are greater than current node, ensuring BST property holds.

Execution Sample

DSA C#

bool IsBST(Node node, int? min, int? max) {
  if (node == null) return true;
  if ((min != null && node.val <= min) || (max != null && 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 recursively.

Execution Table

Step	Operation	Node Visited	Min Allowed	Max Allowed	Check Result	Tree State
1	Start at root	10	null	null	Pass	[10]
2	Check left child	5	null	10	Pass	[10, 5]
3	Check left-left child	2	null	5	Pass	[10, 5, 2]
4	Check left-left-left child	null	null	2	Pass (null)	[10, 5, 2]
5	Check left-left-right child	null	2	5	Pass (null)	[10, 5, 2]
6	Check left-right child	7	5	10	Pass	[10, 5, 2, 7]
7	Check left-right-left child	null	5	7	Pass (null)	[10, 5, 2, 7]
8	Check left-right-right child	null	7	10	Pass (null)	[10, 5, 2, 7]
9	Check right child	15	10	null	Pass	[10, 5, 2, 7, 15]
10	Check right-left child	12	10	15	Pass	[10, 5, 2, 7, 15, 12]
11	Check right-left-left child	null	10	12	Pass (null)	[10, 5, 2, 7, 15, 12]
12	Check right-left-right child	null	12	15	Pass (null)	[10, 5, 2, 7, 15, 12]
13	Check right-right child	20	15	null	Pass	[10, 5, 2, 7, 15, 12, 20]
14	Check right-right-left child	null	15	20	Pass (null)	[10, 5, 2, 7, 15, 12, 20]
15	Check right-right-right child	null	20	null	Pass (null)	[10, 5, 2, 7, 15, 12, 20]
16	All nodes validated	null	null	null	Tree is BST	[10, 5, 2, 7, 15, 12, 20]

💡 All nodes satisfy BST property, recursion ends with True

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 9	After Step 13	Final
node.val	10	10	5	2	7	15	20	null
min	null	null	null	null	5	10	15	null
max	null	null	10	5	10	null	null	null
Tree State	[]	[10]	[10,5]	[10,5,2]	[10,5,2,7]	[10,5,2,7,15]	[10,5,2,7,15,12,20]	[10,5,2,7,15,12,20]

Key Moments - 3 Insights

Why do we pass min and max values during recursion?

Passing min and max helps ensure each node's value fits the BST rules relative to its ancestors, as shown in steps 2, 3, and 9 where these limits guide validation.

What happens when we reach a null node?

When a node is null (steps 4, 5, 7, etc.), we return true because an empty subtree is valid, allowing recursion to continue safely.

Why do we check node.val <= min or node.val >= max?

This check ensures the current node does not violate BST ordering, as seen in step 2 where node 5 must be less than max 10 to pass.

Visual Quiz - 3 Questions

Look at the execution table, what is the min and max allowed when visiting node 7 at step 6?

A min = 2, max = 7

B min = 5, max = 10

C min = null, max = 5

D min = 7, max = 10

💡 Hint

Check the 'Min Allowed' and 'Max Allowed' columns at step 6 in the execution table

At which step does the recursion confirm the right subtree of node 15 is valid?

A Step 15

B Step 10

C Step 13

D Step 16

💡 Hint

Look for the step where node 20 (right-right child) is visited in the execution table

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

A Step 13

B Step 11

C Step 10

D Step 9

💡 Hint

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

Concept Snapshot

Validate BST by recursively checking each node's value lies between min and max bounds.
Start with root (min=null, max=null).
For left child, max = current node's value.
For right child, min = current node's value.
Return false if any node violates bounds.
Return true if all nodes pass.

Full Transcript

To check if a binary tree is a BST, we start at the root and recursively verify that each node's value fits within allowed minimum and maximum limits. These limits come from ancestor nodes to ensure the BST property holds. When visiting a node, if its value is not strictly greater than min and less than max, we return false. If the node is null, we return true since an empty subtree is valid. We update min and max as we go down left and right subtrees respectively. This process continues until all nodes are validated or a violation is found. The execution table shows each step visiting nodes with their min and max bounds and the tree state. Key moments clarify why min and max are needed and how null nodes are handled. The visual quiz tests understanding of these bounds and validation steps.

Practice

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

easy

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

B. Each node has exactly two children

C. All nodes have unique values but no order is required

D. The tree is always 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 A

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 [OK]

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Ignoring the ordering property

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

easy

A. bool IsBST(Node root, int min, int max)

B. void IsBST(Node root)

C. int IsBST(Node root)

D. bool IsBST(Node root, Node parent)

Solution

1. Step 1: Identify parameters needed for BST validation

   To validate BST, we need to check node values within a range (min, max) as we traverse.

2. Step 2: Match method signature with required parameters

   bool IsBST(Node root, int min, int max) includes root node and min/max range, suitable for recursive BST check.

3. Final Answer:

   bool IsBST(Node root, int min, int max) -> Option A

4. Quick Check:

   Method with min/max range = bool IsBST(Node root, int min, int max) [OK]

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

Common Mistakes:

• Using void return type instead of bool
• Missing min and max parameters for range checks
• Passing parent node instead of value ranges

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

class Node {
  public int val;
  public Node left, right;
  public Node(int v) { val = v; left = right = null; }
}

bool IsBST(Node node, int min, int max) {
  if (node == null) return true;
  if (node.val <= min || node.val >= max) return false;
  return IsBST(node.left, min, node.val) && IsBST(node.right, node.val, max);
}

var root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(1);
root.left.right = new Node(12);

Console.WriteLine(IsBST(root, int.MinValue, int.MaxValue));

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Trace the tree structure and BST property

   The tree has root 10, left child 5, right child 15. Left child's right child is 12, which is greater than 10 but in left subtree.

2. Step 2: Check BST validation logic

   IsBST will fail because 12 is in left subtree of 10 but greater than 10, violating BST rules.

3. Final Answer:

   False -> Option B

4. Quick Check:

   Node 12 in left subtree breaks BST = False [OK]

Hint: Check if left subtree nodes are less than root [OK]

Common Mistakes:

• Assuming all nodes are valid without checking subtree ranges
• Ignoring node 12's position violating BST
• Confusing left and right subtree values

4. Identify the bug in the following C# code that checks if a binary tree is a BST:

bool IsBST(Node node) {
  if (node == null) return true;
  if (node.left != null && node.left.val > node.val) return false;
  if (node.right != null && node.right.val < node.val) return false;
  return IsBST(node.left) && IsBST(node.right);
}

medium

A. It should return int instead of bool

B. It uses incorrect comparison operators

C. It does not handle null nodes correctly

D. It does not check the entire subtree values, only immediate children

Solution

1. Step 1: Analyze the checks performed

   The code only compares node values with immediate left and right children, not entire subtrees.

2. Step 2: Understand BST validation requirement

   BST requires all nodes in left subtree < node, and all in right subtree > node, not just immediate children.

3. Final Answer:

   It does not check the entire subtree values, only immediate children -> Option D

4. Quick Check:

   Check full subtree values, not just children [OK]

Hint: Check full subtree ranges, not just direct children [OK]

Common Mistakes:

• Only comparing immediate children values
• Ignoring subtree min/max constraints
• Assuming null handling is incorrect

5. Given a binary tree, how would you modify the standard BST validation to allow duplicate values only on the right subtree?

hard

A. Change the comparison to allow node.val <= max for right subtree and node.val > min for left subtree

B. Allow duplicates only if node.val >= min for left subtree and node.val < max for right subtree

C. Allow duplicates only if node.val > min for left subtree and node.val <= max for right subtree

D. Disallow duplicates completely by strict less than and greater than comparisons

Solution

1. Step 1: Understand duplicate placement rule

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

2. Step 2: Adjust comparison operators accordingly

   Left subtree: node.val > min (strictly less), right subtree: node.val <= max (allow equal or greater).

3. Final Answer:

   Allow duplicates only if node.val > min for left subtree and node.val <= max for right subtree -> Option C

4. Quick Check:

   Duplicates on right subtree use <= max [OK]

Hint: Use <= for right subtree, > for left subtree to allow duplicates right only [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Using <= on left subtree incorrectly
• Disallowing duplicates completely when allowed