Validate if Tree is BST in DSA C#

Mental Model

A binary search tree (BST) has nodes arranged so that left children are smaller and right children are larger than the parent. We check every node to make sure it follows this rule.

Analogy: Imagine a family photo line where everyone shorter stands to the left and taller to the right. If someone is out of order, the line is not correct.

    5
   / \
  3   7
 / \   \
2   4   8

Dry Run Walkthrough

Input: Tree: 5 -> left 3, right 7; 3 -> left 2, right 4; 7 -> right 8

Goal: Check if this tree follows BST rules where left < node < right for all nodes

Step 1: Start at root 5 with allowed range (-∞, +∞)

Node=5, Range=(-∞, +∞)

Why: We begin checking from the root with no limits

Step 2: Check left child 3 with range (-∞, 5)

Node=3, Range=(-∞, 5)

Why: Left child must be less than 5

Step 3: Check left child of 3 which is 2 with range (-∞, 3)

Node=2, Range=(-∞, 3)

Why: Left child of 3 must be less than 3

Step 4: Check right child of 3 which is 4 with range (3, 5)

Node=4, Range=(3, 5)

Why: Right child of 3 must be greater than 3 and less than 5

Step 5: Check right child 7 of root 5 with range (5, +∞)

Node=7, Range=(5, +∞)

Why: Right child must be greater than 5

Step 6: Check right child of 7 which is 8 with range (7, +∞)

Node=8, Range=(7, +∞)

Why: Right child of 7 must be greater than 7

Result:

Tree is a valid BST because all nodes fit their allowed ranges

Annotated Code

DSA C#

using System;

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

class BSTValidator {
    public bool IsValidBST(Node root) {
        return Validate(root, long.MinValue, long.MaxValue);
    }

    private bool Validate(Node node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        // Check left subtree with updated max
        if (!Validate(node.left, min, node.val)) return false;
        // Check right subtree with updated min
        if (!Validate(node.right, node.val, max)) return false;
        return true;
    }
}

class Program {
    static void Main() {
        Node root = new Node(5);
        root.left = new Node(3);
        root.right = new Node(7);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.right = new Node(8);

        BSTValidator validator = new BSTValidator();
        bool result = validator.IsValidBST(root);
        Console.WriteLine(result ? "Tree is a valid BST" : "Tree is NOT a valid BST");
    }
}

if (node == null) return true;

Base case: empty node is valid

if (node.val <= min || node.val >= max) return false;

Check if current node violates BST range rules

if (!Validate(node.left, min, node.val)) return false;

Recursively validate left subtree with updated max limit

if (!Validate(node.right, node.val, max)) return false;

Recursively validate right subtree with updated min limit

return true;

If no violations found, subtree is valid

Output

Tree is a valid BST

Complexity Analysis

Time: O(n) because we visit each node once to check its value

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to checking inorder traversal sortedness, this method checks validity during traversal without extra storage

Edge Cases

Empty tree (root is null)

Returns true because empty tree is valid BST

DSA C#

if (node == null) return true;

Single node tree

Returns true because one node always satisfies BST rules

DSA C#

if (node == null) return true;

Tree with duplicate values

Returns false because duplicates violate strict BST rules (node.val must be strictly less or greater)

DSA C#

if (node.val <= min || node.val >= max) return false;

When to Use This Pattern

When asked if a binary tree is a BST, use range limits during recursion to verify each node fits the BST property.

Common Mistakes

Mistake: Only checking immediate children without considering entire subtree ranges
Fix: Pass down min and max limits to ensure all descendants fit BST rules

Mistake: Allowing duplicates by using <= or >= incorrectly
Fix: Use strict inequalities to reject duplicates

Summary

Checks if a binary tree follows BST rules by verifying node values within allowed ranges.

Use when you need to confirm a tree is a valid BST before operations like search or insert.

The key insight is to track min and max limits for each node to ensure all nodes fit BST ordering.

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