Validate if Tree is BST in DSA C# - Build from Scratch

Validate if Tree is BST

📖 Scenario: You are working with a simple binary tree structure in C#. You want to check if this tree follows the rules of a Binary Search Tree (BST). A BST is a tree where for every node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.This is useful in many real-world applications like searching data quickly or organizing information efficiently.

🎯 Goal: Build a C# program that creates a binary tree, sets up a helper variable, writes a function to check if the tree is a BST, and finally prints the result.

📋 What You'll Learn

Create a binary tree with exact node values and structure

Add a helper method to check BST validity using min and max value limits

Implement the core logic to validate the BST property recursively

Print the final result as 'True' or 'False'

💡 Why This Matters

🌍 Real World

Validating BSTs is important in databases, search engines, and any system that needs fast data lookup and sorting.

💼 Career

Understanding BST validation helps in software engineering roles involving data structures, algorithms, and system design.

1

Create the binary tree nodes

Create a class called Node with an int property Value, and two Node properties Left and Right. Then create the following tree structure by creating Node objects and linking them:
root with value 10,
root.Left with value 5,
root.Right with value 15,
root.Left.Left with value 2,
root.Left.Right with value 7,
root.Right.Right with value 20.

DSA C#

// Define Node class and create the tree nodes as described
// Your code here

Hint

Start by defining the Node class with the required properties and a constructor. Then create the root node and assign its left and right children as described.

2

Add helper method signature for BST validation

Add a method called IsBST that takes three parameters: a Node called node, an int? called min, and an int? called max. This method will return a bool. For now, just add the method signature and return true inside it.

DSA C#

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

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.Right = new Node(20);

// Add IsBST method signature below
// Your code here

Hint

Define the method IsBST with the specified parameters and return type. For now, just return true to complete the method.

3

Implement BST validation logic

Inside the IsBST method, implement the logic to check if the tree is a BST:
- If node is null, return true.
- If min is not null and node.Value is less than or equal to min, return false.
- If max is not null and node.Value is greater than or equal to max, return false.
- Recursively check the left subtree with updated max as node.Value.
- Recursively check the right subtree with updated min as node.Value.
- Return true only if both subtrees are valid BSTs.

DSA C#

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

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.Right = new Node(20);

// Implement the IsBST method logic below
// Your code here

Hint

Use the rules of BST to check the current node's value against min and max limits. Then recursively check left and right subtrees with updated limits.

4

Print the result of BST validation

Call the IsBST method with root, null for min, and null for max. Print the returned boolean value.

DSA C#

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

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.Right = new Node(20);

bool IsBST(Node node, int? min, int? max)
{
    if (node == null)
        return true;

    if (min != null && node.Value = max)
        return false;

    bool leftIsBST = IsBST(node.Left, min, node.Value);
    bool rightIsBST = IsBST(node.Right, node.Value, max);

    return leftIsBST && rightIsBST;
}

// Call IsBST and print the result below
// Your code here

Hint

Call IsBST with root, null, and null. Use Console.WriteLine to print the result.

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