Validate if Tree is BST in DSA Javascript

Mental Model

A binary search tree (BST) is a tree where every left child is smaller and every right child is bigger than the current node.

Analogy: Think of a family tree where every child on the left side is younger than their parent, and every child on the right side is older, keeping the order clear.

    5
   / \
  3   7
 / \   \
2   4   8

Dry Run Walkthrough

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

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

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

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

Why: We begin with no limits for the root

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: 2 with range (-∞, 3)

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

Why: Left child must be less than 3

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

Node=4, Range=(3, 5)

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

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

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

Why: Right child must be greater than 5

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

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

Why: Right child must be greater than 7

Result:

Tree is a valid BST

Annotated Code

DSA Javascript

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

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

// Driver code
const root = new TreeNode(5,
  new TreeNode(3, new TreeNode(2), new TreeNode(4)),
  new TreeNode(7, null, new TreeNode(8))
);

console.log(isValidBST(root) ? "Tree is a valid BST" : "Tree is NOT a valid BST");

if (root === null) return true;

Base case: empty subtree is valid BST

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

Check if current node violates BST range rules

return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);

Recursively check left and right subtrees with updated ranges

Output

Tree is a valid BST

Complexity Analysis

Time: O(n) because we visit every node once

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

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

Edge Cases

Empty tree

Returns true because empty tree is a valid BST

DSA Javascript

if (root === null) return true;

Single node tree

Returns true because one node is always a valid BST

DSA Javascript

if (root === null) return true;

Tree with duplicate values

Returns false because BST does not allow duplicates in this implementation

DSA Javascript

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

When to Use This Pattern

When you need to confirm if a tree follows the BST rules, use range checks during recursion to validate each node fits the allowed min-max limits.

Common Mistakes

Mistake: Only checking immediate children without considering the full allowed range
Fix: Pass down min and max limits to ensure all descendants respect BST ordering

Summary

Checks if a binary tree follows the BST ordering rules using min-max range validation.

Use when you want to verify if a tree is a valid BST efficiently.

The key insight is to track allowed value ranges for each node during recursion.