Validate if Tree is BST in DSA Javascript - 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 is organized for fast searching.

Why it matters

Without knowing if a tree is a BST, we can't trust operations like searching, inserting, or deleting to work efficiently. If the tree isn't a BST, these operations might become slow, like searching through a messy pile instead of a sorted list. 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 this, you can explore tree operations like insertion, deletion, and traversal in BSTs, and then move on to 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 true for every book on the shelf, the shelf is well organized like a BST.

       10
      /  \
     5    15
    / \     \
   2   7     20

Each node follows: left < node < right

Build-Up - 7 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 holds a value. The tree starts from a root node and branches down. Example: const root = { value: 10, left: { value: 5, left: null, right: null }, right: { value: 15, left: null, right: null } };

Result

A simple tree with root 10, left child 5, and right child 15.

Understanding the basic shape and connections of a binary tree is essential before checking any special rules like BST.

2

Foundation

Know BST Property Definition

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 are smaller than the node's value. - All values in the right subtree are greater than the node's value. This rule applies recursively to every node in the tree.

Result

Clear rule to check if a tree is a BST.

Grasping this rule is the foundation for validating BSTs and understanding their efficiency.

3

Intermediate

Validate BST Using 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 minimum and maximum allowed values to check each node's validity recursively.

We check each node's value is within allowed min and max limits. Initially, min is -Infinity and max is +Infinity. For left child, max becomes current node's value. For right child, min becomes current node's value. 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); }

Result

Returns true if tree is BST, false otherwise.

Using range limits ensures we check the entire subtree's values, not just immediate children, preventing subtle BST violations.

4

Intermediate

Validate BST Using Inorder Traversal

🤔Before reading on: Will an inorder traversal of a BST produce a sorted list? Commit to yes or no.

Concept: Traverse the tree inorder and check if the values come out sorted ascending.

Inorder traversal visits nodes left-root-right. For BST, this produces sorted values. function isBSTInorder(root) { let prev = null; function inorder(node) { if (!node) return true; if (!inorder(node.left)) return false; if (prev !== null && node.value <= prev) return false; prev = node.value; return inorder(node.right); } return inorder(root); }

Result

Returns true if inorder traversal is sorted, meaning tree is BST.

Checking sorted order during inorder traversal is a simple way to validate BST without extra parameters.

5

Intermediate

Compare Both Validation Methods

🤔Before reading on: Which method do you think is more efficient or easier to implement? Commit to your answer.

Concept: Understand pros and cons of range check vs inorder traversal methods.

Range check method passes min/max limits down recursion, catching violations early. Inorder method uses a single variable to track previous value, simpler but requires careful state management. Both run in O(n) time, visiting each node once. Example trees can be tested with both methods to see they agree.

Result

Both methods correctly validate BST property.

Knowing multiple methods helps choose the best tool depending on context and coding style.

6

Advanced

Handle Edge Cases in BST Validation

🤔Before reading on: Should duplicate values be allowed in a BST? Commit to yes or no.

Concept: Decide how to treat duplicates and handle empty trees or single-node trees.

BSTs usually do not allow duplicates or place duplicates consistently (e.g., always right). Empty trees are valid BSTs. Single-node trees are always valid BSTs. Adjust validation code to handle these cases explicitly. Example: change <= to < or <= depending on duplicate policy.

Result

Validation correctly handles edge cases and duplicates as per chosen rules.

Understanding edge cases prevents bugs and clarifies BST definition variations in real systems.

7

Expert

Optimize Validation for Large Trees

🤔Before reading on: Can BST validation be done without recursion? Commit to yes or no.

Concept: Use iterative inorder traversal with a stack to avoid recursion and reduce call stack overhead.

Recursive calls can cause stack overflow on deep trees. Iterative inorder traversal uses an explicit stack: function isBSTIterative(root) { let stack = []; let prev = null; let current = root; while (stack.length > 0 || current !== null) { while (current !== null) { stack.push(current); current = current.left; } current = stack.pop(); if (prev !== null && current.value <= prev) return false; prev = current.value; current = current.right; } return true; }

Result

Validates BST without recursion, safe for very deep trees.

Knowing iterative methods helps write robust code that works in all environments, especially with large data.

Under the Hood

BST validation works by ensuring every node respects the ordering constraints relative to all its ancestors, not just its parent. The range check method propagates allowed value ranges down the tree, pruning invalid subtrees early. The inorder method relies on the property that inorder traversal of a BST produces sorted values, so any deviation means violation. Internally, the recursion or iteration visits each node once, checking conditions and passing state.

Why designed this way?

The BST property was designed to allow fast search, insert, and delete operations by maintaining order. Validation methods reflect this by checking ordering constraints globally (range method) or locally in traversal order (inorder method). Alternatives like checking only immediate children fail because they miss violations deeper in subtrees.

Validation Flow:

[Start at root]
     |
[Check node value in (min, max)]
     |
[Left subtree: max = node.value]
     |
[Right subtree: min = node.value]
     |
[Repeat recursively]

OR

[Inorder traversal]
     |
[Visit left subtree]
     |
[Check current node value > previous]
     |
[Visit right subtree]
     |
[If all checks pass, tree is BST]

Myth Busters - 4 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. The entire left subtree must have smaller values, not just the immediate child.

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

Quick: Does inorder traversal always produce sorted values for any binary tree? Commit yes or no.

Common Belief: Inorder traversal always gives sorted values regardless of tree type.

Reality: Only BSTs produce sorted inorder traversal. Other binary trees can produce unordered sequences.

Why it matters: Misunderstanding this can cause wrong assumptions about tree structure and lead to incorrect algorithms.

Quick: Should duplicate values be allowed anywhere in a BST? Commit yes or no.

Common Belief: BSTs allow duplicate values anywhere without restrictions.

Reality: BSTs usually disallow duplicates or require a consistent rule (e.g., duplicates always go to right subtree).

Why it matters: Ignoring this can cause inconsistent tree structure and break search or insert logic.

Quick: Can recursive BST validation cause problems on very deep trees? Commit yes or no.

Common Belief: Recursion is always safe and efficient for BST validation.

Reality: Deep trees can cause stack overflow with recursion; iterative methods are safer.

Why it matters: Not handling this can cause crashes or failures in production systems with large data.

Expert Zone

1

Range limits must be strict inequalities to avoid subtle bugs with duplicates.

2

Inorder traversal validation requires careful handling of previous value state to avoid false negatives.

3

Iterative validation is preferred in environments with limited stack size or very deep trees.

When NOT to use

If the tree allows duplicates with complex rules or is not a binary tree, these BST validation methods may fail. For balanced trees like AVL or Red-Black, specialized validation is needed. For non-binary trees, other ordering checks apply.

Production Patterns

In real systems, BST validation is used during debugging, data integrity checks, and before performing operations that assume BST properties. Iterative inorder validation is common in embedded systems to avoid recursion. Range check is preferred in recursive-friendly environments for clarity.

Connections

Binary Tree Traversals

Builds-on

Understanding inorder traversal is key to validating BSTs because it reveals the sorted order property unique to BSTs.

Balanced Trees (AVL, Red-Black Trees)

Advanced extension

Validating BST property is a prerequisite before checking balance conditions in self-balancing trees, which maintain BST order plus height constraints.

Sorting Algorithms

Conceptual similarity

The BST property ensures data is organized like a sorted list, linking tree validation to sorting concepts and enabling efficient search.

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 entire subtrees, not just immediate children.

#2 Allowing duplicates without consistent rule.

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; // strict inequalities
return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}

Root cause:

Not enforcing strict inequalities causes duplicates to violate BST rules silently.

#3 Using recursion without considering stack limits.

Wrong 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);
}
// called on very deep tree

Correct approach:

function isBSTIterative(root) {
let stack = [];
let prev = null;
let current = root;
while (stack.length > 0 || current !== null) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (prev !== null && current.value <= prev) return false;
prev = current.value;
current = current.right;
}
return true;
}

Root cause:

Ignoring recursion depth limits can cause runtime errors on large trees.

Key Takeaways

A BST requires every node's left subtree to have smaller values and right subtree to have larger values, not just immediate children.

Validating BST can be done using range limits passed down recursion or by checking if inorder traversal produces sorted values.

Edge cases like duplicates and empty trees must be handled carefully to avoid incorrect validation.

Iterative inorder traversal is a robust alternative to recursion for validating very deep trees.

Understanding BST validation is essential for trusting tree operations and building efficient search structures.

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. Every node's left child is smaller and right child is larger than the node

C. All nodes have the same value

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

Solution

1. Step 1: Understand BST property

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

2. Step 2: Compare options with definition

   Every node's left child is smaller and right child is larger than the node correctly states this property. Other options describe different tree properties.

3. Final Answer:

   Every node's left child is smaller and right child is larger than the node -> Option B

4. Quick Check:

   BST property = Every node's left child is smaller and right child is larger than the node [OK]

Hint: BST means left < node < right for every node [OK]

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Assuming all values are equal

2. Which of the following JavaScript function signatures is correct to check if a binary tree is a BST?

easy

A. function isBST(node, min, max) {}

B. function isBST(node, left, right, parent) {}

C. function checkBST(root) {}

D. function validateBST(tree, minVal) {}

Solution

1. Step 1: Identify common BST validation parameters

   To validate BST, we usually pass the current node and allowed min and max values to check constraints.

2. Step 2: Match function signatures

   function isBST(node, min, max) {} matches this pattern with node, min, and max parameters. Others have extra or missing parameters.

3. Final Answer:

   function isBST(node, min, max) {} -> Option A

4. Quick Check:

   Correct BST function signature = function isBST(node, min, max) {} [OK]

Hint: Use min and max limits to check BST recursively [OK]

Common Mistakes:

• Adding unnecessary parameters
• Missing min or max limits
• Using wrong parameter names

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

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

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

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

medium

A. undefined

B. true

C. false

D. TypeError

Solution

1. Step 1: Analyze tree structure

   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 left child of 15 but 6 < 10, which violates BST property because all right subtree nodes must be > 10.

3. Final Answer:

   false -> Option C

4. Quick Check:

   6 in right subtree < 10 breaks BST = false [OK]

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

Common Mistakes:

• Ignoring subtree value constraints
• Assuming all children just compare with parent
• Missing base case for null nodes

4. Find the bug in this BST validation function and select the fix:

function isBST(node) {
  if (!node) return true;
  if (node.left && node.left.val >= node.val) return false;
  if (node.right && node.right.val <= node.val) return false;
  return isBST(node.left) && isBST(node.right);
}

medium

A. Add min and max parameters to track value ranges

B. Change >= to > and <= to < in comparisons

C. Return false if node is null

D. Remove recursive calls to isBST

Solution

1. Step 1: Understand current checks

   Function only compares immediate children with current node, missing subtree constraints.

2. Step 2: Identify fix

   To correctly validate BST, function must track allowed min and max values for each subtree, not just immediate children.

3. Final Answer:

   Add min and max parameters to track value ranges -> Option A

4. Quick Check:

   Use min/max limits to validate BST correctly [OK]

Hint: Use min/max limits, not just immediate child values [OK]

Common Mistakes:

• Only checking immediate children
• Ignoring subtree value constraints
• Not using recursion properly

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 node.val <= min and node.val >= max checks in the recursive function.

hard

A. Allow duplicates by changing left subtree check to node.val < min and right subtree check to node.val > max

B. Allow duplicates on right by changing left subtree check to node.val <= min and right subtree check to node.val > max

C. Allow duplicates on right by changing left subtree check to node.val <= min and right subtree check to node.val >= max

D. Allow duplicates on right by changing left subtree check to node.val < min and right subtree check to node.val >= max

Solution

1. Step 1: Understand duplicates in BST

   Allowing duplicates only on right means left subtree nodes must be strictly less than current node, right subtree nodes can be greater or equal.

2. Step 2: Adjust min/max checks accordingly

   Left subtree check should be node.val < min (strictly less), right subtree check should be node.val >= max (allow equal).

3. Final Answer:

   Allow duplicates on right by changing left subtree check to node.val < min and right subtree check to node.val >= max -> Option D

4. Quick Check:

   Duplicates only right: left < node, right >= node [OK]

Hint: Strict less on left, allow equal on right for duplicates [OK]

Common Mistakes:

• Allowing duplicates on both sides
• Using non-strict inequalities on left subtree
• Confusing min and max checks