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.

Practice

1. What does it mean for a binary tree to be a Binary Search Tree (BST)?

easy

A. Every node has exactly two children

B. The tree is balanced with equal height on both sides

C. All nodes have the same value

D. Every node's left subtree has smaller values and right subtree has larger values

Solution

1. Step 1: Understand BST property

   A BST requires that for each node, all values in the left subtree are smaller and all values in the right subtree are larger.

2. Step 2: Compare options with definition

   Every node's left subtree has smaller values and right subtree has larger values matches the BST property exactly, while others describe different tree properties.

3. Final Answer:

   Every node's left subtree has smaller values and right subtree has larger values -> Option D

4. Quick Check:

   BST property = Every node's left subtree has smaller values and right subtree has larger values [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 all values are equal

2. Which TypeScript function signature correctly represents a function to check if a binary tree is a BST?

easy

A. function isBST(root: any): void

B. function isBST(root: TreeNode | null): boolean

C. function isBST(root: TreeNode): number

D. function isBST(root: number): boolean

Solution

1. Step 1: Identify correct parameter and return types

   The function should accept a tree node or null and return a boolean indicating if it is a BST.

2. Step 2: Match options with correct signature

   function isBST(root: TreeNode | null): boolean matches this: input is TreeNode or null, output is boolean. Others have wrong types or return types.

3. Final Answer:

   function isBST(root: TreeNode | null): boolean -> Option B

4. Quick Check:

   Correct signature = function isBST(root: TreeNode | null): boolean [OK]

Hint: Input is root node or null, output is true/false [OK]

Common Mistakes:

• Using wrong parameter type like number
• Returning number instead of boolean
• Using void return type

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

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isBST(root: TreeNode | null, min: number = -Infinity, max: number = Infinity): boolean {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
}

const tree = new TreeNode(10, new TreeNode(5), new TreeNode(15, new TreeNode(6), new TreeNode(20)));
console.log(isBST(tree));

medium

A. SyntaxError

B. true

C. false

D. RuntimeError

Solution

1. Step 1: Analyze the tree structure

   The root is 10, left child 5 (valid), right child 15 with left child 6 and right child 20.

2. Step 2: Check BST property on right subtree

   Node 6 is in right subtree of 10 but less than 10, violating BST property. So function returns false.

3. Final Answer:

   false -> Option C

4. Quick Check:

   6 in right subtree < 10 = false [OK]

Hint: Check if left < node < right recursively [OK]

Common Mistakes:

• Ignoring min/max constraints in recursion
• Assuming all subtrees are BST without checks
• Confusing node values in subtrees

4. Identify the bug in this TypeScript function to check if a tree is BST:

function isBST(root: TreeNode | null): boolean {
  if (!root) return true;
  if (root.left && root.left.val > root.val) return false;
  if (root.right && root.right.val < root.val) return false;
  return isBST(root.left) && isBST(root.right);
}

medium

A. It does not check the entire subtree values against min/max limits

B. It uses wrong comparison operators for left and right children

C. It returns true for null nodes incorrectly

D. It does not handle empty tree input

Solution

1. Step 1: Understand the function checks

   The function only compares immediate children values with current node, not entire subtree ranges.

2. Step 2: Explain why this is a bug

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

3. Final Answer:

   It does not check the entire subtree values against min/max limits -> Option A

4. Quick Check:

   Missing min/max range check = It does not check the entire subtree values against min/max limits [OK]

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

Common Mistakes:

• Only comparing direct children values
• Ignoring recursive min/max constraints
• Assuming null nodes cause errors

5. Given a binary tree where nodes can have duplicate values, which modification to the BST validation logic allows duplicates only on the right subtree? Choose the correct condition to replace root.val <= min in the validation function:

function isBST(root: TreeNode | null, min: number = -Infinity, max: number = Infinity): boolean {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
}

hard

A. Change to root.val < min to allow duplicates on right

B. Change to root.val <= min and root.val < max

C. Change to root.val < min and root.val <= max

D. Change to root.val <= min and root.val <= max

Solution

1. Step 1: Understand duplicates on right subtree rule

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

2. Step 2: Adjust min/max comparisons accordingly

   Replace root.val <= min with root.val < min. This fails only if strictly less than min (allows equal to min on right recursion), keeping root.val >= max for strict upper bound.

3. Final Answer:

   Change to root.val < min to allow duplicates on right -> Option A

4. Quick Check:

   Duplicates right subtree = Change to root.val < min [OK]

Hint: Use strict less on left, less or equal on right for duplicates [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Using <= on both sides
• Not changing min/max checks