Validate if Tree is BST in DSA C - Deep Dive

Overview - Validate if Tree is BST

What is it?

A Binary Search Tree (BST) is a special kind of tree where each node has at most two children. For every node, all values in its left subtree are smaller, and all values in its right subtree are larger. Validating if a tree is a BST means checking if this rule holds true for every node in the tree. This helps ensure the tree can be used for fast searching and sorting.

Why it matters

Without knowing if a tree is a BST, we cannot trust operations like searching, inserting, or deleting to work efficiently. If the tree breaks the BST rules, these operations might become slow or incorrect. Validating a BST helps maintain data integrity and performance in many software systems like databases and file systems.

Where it fits

Before this, you should understand basic tree structures and recursion. After learning this, you can explore tree operations like insertion, deletion, and balanced trees such as AVL or Red-Black trees.

Mental Model

Core Idea

A tree is a BST if every node's left subtree has smaller values and the right subtree has larger values, consistently throughout the tree.

Think of it like...

Imagine a library where books are arranged so that all books on the left shelf have earlier publication years than the current book, and all books on the right shelf have later publication years. Checking if the library is organized this way is like validating a BST.

        10
       /  \
      5    15
     / \     \
    2   7     20

Each node follows: left < node < right

Build-Up - 6 Steps

1

Foundation

Understand Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. Each node stores a value and pointers to its children or NULL if none exist. This structure allows hierarchical data storage.

Result

You can represent data in a tree form with nodes connected by left and right links.

Understanding the basic tree structure is essential before checking any special properties like BST rules.

2

Foundation

Know BST Property Basics

Concept: Learn the rule that defines a BST: left subtree values < node < right subtree values.

In a BST, for every node, all values in the left subtree must be smaller than the node's value, and all values in the right subtree must be larger. This rule applies recursively to every node.

Result

You can identify if a tree might be a BST by checking this property at each node.

Knowing the BST property helps you understand what to check when validating a tree.

3

Intermediate

Recursive Validation with Range Limits

🤔Before reading on: Do you think checking only immediate children is enough to validate a BST? Commit to yes or no.

Concept: Use recursion with min and max limits to validate the BST property for all nodes.

To validate a BST, we check each node's value against allowed min and max limits. Initially, these limits are very wide (like negative and positive infinity). For the left child, the max limit becomes the current node's value; for the right child, the min limit becomes the current node's value. Recursively applying this ensures all nodes respect BST rules.

Result

You can correctly identify if a tree is a BST by ensuring every node fits within its allowed range.

Understanding that BST validation requires checking the entire subtree range, not just immediate children, prevents common mistakes.

4

Intermediate

Implementing Validation in C

🤔Before reading on: Will a simple in-order traversal without limits always confirm a BST? Commit to yes or no.

Concept: Write a C function that uses recursion and range limits to validate a BST.

We define a function isBST that takes a node and min/max values. If the node is NULL, return true. Check if node's value is within min and max. Recursively check left subtree with updated max and right subtree with updated min. Return true only if both subtrees are valid.

Result

A working C function that returns true if the tree is a BST, false otherwise.

Knowing how to implement the range check in code solidifies the mental model and prepares for real-world use.

5

Advanced

In-Order Traversal Validation Method

🤔Before reading on: Can in-order traversal alone detect all BST violations? Commit to yes or no.

Concept: Validate BST by checking if in-order traversal produces a sorted sequence.

In-order traversal of a BST visits nodes in ascending order. We traverse the tree in-order, keeping track of the previously visited node's value. If at any point the current node's value is not greater than the previous, the tree is not a BST.

Result

You can confirm BST validity by ensuring the in-order sequence is strictly increasing.

Understanding this method offers an alternative approach that is often simpler to implement and debug.

6

Expert

Handling Edge Cases and Integer Limits

🤔Before reading on: Do you think using INT_MIN and INT_MAX as initial limits can cause bugs? Commit to yes or no.

Concept: Consider edge cases like duplicate values and integer boundary values in BST validation.

Using INT_MIN and INT_MAX as initial limits can cause issues if node values equal these limits. Also, BSTs usually do not allow duplicate values or define a rule for them (e.g., duplicates on left or right). The validation function must handle these carefully, possibly by using long long types or custom rules for duplicates.

Result

A robust BST validation that correctly handles all edge cases and avoids false positives or negatives.

Knowing these subtleties prevents subtle bugs in production systems where data ranges are large or duplicates exist.

Under the Hood

The validation works by recursively narrowing the allowed value range for each node. Initially, the range is infinite. When moving left, the upper bound becomes the parent node's value; when moving right, the lower bound becomes the parent node's value. This ensures no node violates the BST property anywhere in the tree, not just locally.

Why designed this way?

This approach was chosen because checking only immediate children is insufficient; violations can occur deeper in subtrees. Using min/max limits captures the global ordering constraints efficiently. Alternatives like full subtree scans are less efficient.

Root Node
  ├─ Left Subtree (values < Root)
  │     ├─ Left Child (max = Root value)
  │     └─ ...
  └─ Right Subtree (values > Root)
        ├─ Right Child (min = Root value)
        └─ ...

Myth Busters - 3 Common Misconceptions

Quick: Is it enough to check only if left child < node and right child > node to confirm a BST? Commit to yes or no.

Common Belief: If each node's immediate left child is smaller and right child is larger, the tree is a BST.

Reality: This is false because violations can occur deeper in the subtree, not just at immediate children.

Why it matters: Relying on this leads to incorrect validation, causing bugs in search or insert operations.

Quick: Does an in-order traversal always produce a sorted list for any binary tree? Commit to yes or no.

Common Belief: In-order traversal always gives a sorted list, so it's enough to check the traversal order.

Reality: Only BSTs produce sorted in-order traversals. Non-BST trees can produce unsorted sequences.

Why it matters: Misunderstanding this can cause false positives when validating BSTs.

Quick: Can duplicate values exist anywhere in a BST without breaking its property? Commit to yes or no.

Common Belief: BSTs allow duplicate values anywhere without special rules.

Reality: BSTs usually define a rule for duplicates (e.g., all duplicates go to left or right subtree). Ignoring this breaks the BST property.

Why it matters: Ignoring duplicates leads to inconsistent tree behavior and validation errors.

Expert Zone

1

BST validation must consider the entire subtree range, not just immediate children, to avoid subtle bugs.

2

Handling duplicates requires a clear rule; otherwise, the BST property is ambiguous.

3

Integer boundary values can cause overflow or incorrect comparisons if not handled with wider types or careful logic.

When NOT to use

This validation approach is not suitable for trees that allow duplicates without a strict ordering rule or for non-binary trees. For balanced trees like AVL or Red-Black, additional properties must be checked beyond BST validation.

Production Patterns

In real systems, BST validation is used during tree construction, debugging, and before performing operations that assume BST properties. It is often combined with balancing checks in self-balancing trees.

Connections

In-Order Tree Traversal

Builds-on

Understanding in-order traversal helps grasp why BSTs produce sorted sequences and how this property can be used for validation.

Range Checking in Algorithms

Same pattern

The min/max range checking pattern used in BST validation appears in other algorithms that enforce constraints recursively, like interval trees or segment trees.

Library Book Sorting Systems

Analogous real-world system

Knowing how libraries organize books by publication year or author helps understand BST ordering and validation in a practical context.

Common Pitfalls

#1 Checking only immediate children for BST property.

Wrong approach:

bool isBST(Node* node) {
if (!node) return true;
if (node->left && node->left->value >= node->value) return false;
if (node->right && node->right->value <= node->value) return false;
return isBST(node->left) && isBST(node->right);
}

Correct approach:

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

bool isBST(Node* root) {
return isBSTUtil(root, INT_MIN, INT_MAX);
}

Root cause:

Misunderstanding that BST property applies globally, not just locally at each node.

#2 Using INT_MIN and INT_MAX directly without considering node values equal to these limits.

Wrong approach:

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

Correct approach:

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

bool isBST(Node* root) {
return isBSTUtil(root, LLONG_MIN, LLONG_MAX);
}

Root cause:

Not accounting for inclusive vs exclusive bounds and integer overflow.

Key Takeaways

A BST requires every node's left subtree to have smaller values and right subtree to have larger values, recursively.

Validating a BST needs checking the entire subtree range using min and max limits, not just immediate children.

In-order traversal of a BST produces a sorted sequence, which can be used as an alternative validation method.

Edge cases like duplicates and integer limits must be handled carefully to avoid incorrect validation.

Understanding these principles ensures reliable and efficient use of BSTs in real-world applications.

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