Validate if Tree is BST in DSA Typescript - 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, you can't trust operations like searching or inserting to work efficiently. If the tree breaks the BST rules, searching might become slow, like looking for a book in a messy pile instead of a sorted shelf. Validating the BST property helps keep data organized and operations fast, which is crucial in many software systems.

Where it fits

Before this, you should understand basic trees and binary trees. After learning to validate BSTs, you can explore tree operations like insertion, deletion, and balanced trees like AVL or Red-Black trees.

Mental Model

Core Idea

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

Think of it like...

Imagine a library shelf where all books to the left are alphabetically before the current book, and all books to the right come after it. If this order is kept for every book, finding a book is quick and easy.

       10
      /  \
     5    15
    / \     \
   2   7     20

Each node respects: left < node < right

Build-Up - 6 Steps

1

Foundation

Understand Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children called left and right. Each node holds a value. For example, a node with value 10 can have a left child 5 and right child 15.

Result

You can represent data in a tree shape where each node points to up to two others.

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

2

Foundation

Learn BST Property Definition

Concept: The BST property means left subtree values are smaller, right subtree values are larger than the node's value.

For every node: - All values in the left subtree < node's value - All values in the right subtree > node's value This must hold true for every node in the tree.

Result

You know the rule that makes a binary tree a BST.

Knowing this rule helps you check if a tree is organized for efficient searching.

3

Intermediate

Check BST Using Min-Max Limits

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

Concept: Use a range (min and max) to check if each node's value fits the BST rules recursively.

Start at the root with min = -∞ and max = +∞. For each node: - Check if node's value is between min and max. - Recursively check left child with updated max = node's value. - Recursively check right child with updated min = node's value. If all nodes fit, the tree is a BST.

Result

You can correctly validate BSTs even when violations are deep in the tree.

Using min-max limits prevents false positives that happen if you only check immediate children.

4

Intermediate

Implement Recursive BST Validation

🤔Before reading on: Will an in-order traversal always confirm BST validity? Commit to yes or no.

Concept: Use recursion with min-max checks to implement the validation function.

function isBST(node, min = -Infinity, max = Infinity): boolean { if (node == null) return true; if (node.value <= min || node.value >= max) return false; return isBST(node.left, min, node.value) && isBST(node.right, node.value, max); } This checks every node fits the BST property.

Result

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

Recursion naturally fits tree structures and helps check all nodes with correct limits.

5

Advanced

Validate BST Using In-Order Traversal

🤔Before reading on: Does an in-order traversal produce sorted values only if the tree is a BST? Commit to yes or no.

Concept: In-order traversal visits nodes in ascending order if the tree is a BST.

Traverse the tree in-order (left, node, right). Keep track of the last visited node's value. If current node's value is not greater than last visited, tree is not BST. Example code: let prev = null; function isBSTInOrder(node) { if (!node) return true; if (!isBSTInOrder(node.left)) return false; if (prev !== null && node.value <= prev) return false; prev = node.value; return isBSTInOrder(node.right); }

Result

You get a boolean indicating BST validity by checking sorted order during traversal.

In-order traversal leverages BST's sorted property, offering an alternative validation method.

6

Expert

Handle Edge Cases and Duplicate Values

🤔Before reading on: Should duplicate values be allowed on left or right subtree in a BST? Commit to your answer.

Concept: BST definitions vary on duplicates; handling them correctly avoids bugs.

Some BSTs allow duplicates only on one side (e.g., right subtree). Adjust validation accordingly: - For duplicates allowed on right: use < for left subtree, <= for right subtree. - For strict BST: no duplicates allowed. Example adjustment: if (node.value < min || node.value >= max) return false; // for duplicates on right Testing with duplicates ensures your validation matches the BST variant used.

Result

You can validate BSTs correctly even with duplicates, avoiding false failures or passes.

Knowing how duplicates are handled prevents subtle bugs in real-world BST validations.

Under the Hood

The validation works by recursively checking each node's value against allowed min and max bounds derived from ancestors. This ensures no subtree violates the BST ordering, not just immediate children. The recursion stack keeps track of these bounds as it moves down the tree.

Why designed this way?

This approach was chosen because checking only immediate children misses violations deeper in the tree. The min-max method efficiently propagates constraints from ancestors to descendants, ensuring correctness with minimal overhead.

Root Node
  ├─ Left Subtree (values < root)
  │     ├─ Left Child (values < parent)
  │     └─ Right Child (values > parent)
  └─ Right Subtree (values > root)
        ├─ Left Child (values < parent)
        └─ Right Child (values > parent)

Validation passes min-max bounds down these branches.

Myth Busters - 3 Common Misconceptions

Quick: Is it enough to check only if left child < node and right child > node to confirm BST? Commit 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 subtrees, not just 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 sorted values for any binary tree? Commit yes or no.

Common Belief: In-order traversal always gives sorted values regardless of tree type.

Reality: Only BSTs produce sorted values in in-order traversal; other trees do not guarantee this.

Why it matters: Assuming sorted output from in-order traversal on non-BSTs can cause wrong conclusions about tree order.

Quick: Can duplicates appear anywhere in a BST without breaking its property? Commit yes or no.

Common Belief: Duplicates can be anywhere in a BST without affecting its validity.

Reality: BST definitions vary; duplicates must be placed consistently (e.g., always right subtree) or disallowed.

Why it matters: Ignoring duplicate rules causes inconsistent trees and bugs in search or insert.

Expert Zone

1

The min-max validation approach is more general and handles complex BST variants better than simple child comparisons.

2

In-order traversal validation requires careful state management (like a previous value variable) to avoid false negatives.

3

Handling duplicates consistently is critical in production BSTs to maintain balanced trees and predictable behavior.

When NOT to use

If the tree is not binary or does not follow BST ordering (e.g., heaps, general trees), this validation is not applicable. For balanced BSTs like AVL or Red-Black trees, additional properties must be checked beyond simple BST validation.

Production Patterns

In real systems, BST validation is used during debugging, data integrity checks, and before performing operations that assume BST properties. It is also foundational for implementing balanced trees and database indexing structures.

Connections

In-Order Tree Traversal

Builds-on

Understanding in-order traversal helps grasp why BSTs produce sorted sequences and how to validate them efficiently.

Binary Tree

Prerequisite

Knowing binary tree structure is essential before learning BST validation since BST is a special binary tree.

Sorting Algorithms

Related concept

BST validation connects to sorting because a BST's in-order traversal outputs sorted data, linking tree structures to sorting principles.

Common Pitfalls

#1 Checking only immediate children for BST property.

Wrong approach:

function isBST(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:

function isBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.value <= min || node.value >= max) return false;
return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}

Root cause:

Misunderstanding that BST property applies to all descendants, not just immediate children.

#2 Not resetting or tracking previous value in in-order traversal validation.

Wrong approach:

let prev = null;
function isBSTInOrder(node) {
if (!node) return true;
if (!isBSTInOrder(node.left)) return false;
if (node.value <= prev) return false; // prev never updated
return isBSTInOrder(node.right);
}

Correct approach:

let prev = null;
function isBSTInOrder(node) {
if (!node) return true;
if (!isBSTInOrder(node.left)) return false;
if (prev !== null && node.value <= prev) return false;
prev = node.value;
return isBSTInOrder(node.right);
}

Root cause:

Forgetting to update the previous value after visiting a node.

#3 Ignoring how duplicates are handled in BST validation.

Wrong approach:

function isBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.value < min || node.value > max) return false; // allows duplicates anywhere
return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}

Correct approach:

function isBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.value < min || node.value >= max) return false; // duplicates only on right
return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}

Root cause:

Not defining or enforcing duplicate placement rules in BST.

Key Takeaways

A BST requires every node's left subtree to have smaller values and right subtree to have larger values, consistently throughout the tree.

Validating a BST by checking only immediate children is incorrect; you must check all descendants using min-max bounds.

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

Handling duplicates in BSTs requires clear rules to avoid validation errors and maintain tree integrity.

Understanding these principles ensures reliable BST operations and efficient data management in software.