Validate if Tree is BST in DSA Typescript

Mental Model

A binary search tree (BST) is a tree where every node's left child is smaller and right child is bigger than the node itself. We check this by making sure all nodes follow this rule from top to bottom.

Analogy: Imagine a family tree where every parent is older than their children on the right side and younger than their children on the left side. To check if the tree is correct, you verify each parent's age fits this rule with their children.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

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

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

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

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

Why: We begin checking from the root with no limits

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

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

Why: Left child must be less than 3

Step 4: Check right child of 3 which is 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 of root 5 with range (5, +∞)

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

Why: Right child must be greater than 5

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

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

Why: Right child must be greater than 7

Result:

Tree is a valid BST because all nodes fit their allowed ranges

Annotated Code

DSA Typescript

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

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

// Driver code to test the example tree
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 (node === null) return true;

Base case: empty node means no violation

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

Check if current node violates BST range rules

return helper(node.left, min, node.val) && helper(node.right, node.val, max);

Recursively check left subtree with updated max and right subtree with updated min

Output

Tree is a valid BST

Complexity Analysis

Time: O(n) because we visit each node once to check BST property

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

vs Alternative: Compared to inorder traversal checking sorted order, this method checks BST property directly with ranges, avoiding extra storage

Edge Cases

Empty tree (root is null)

Returns true because empty tree is a valid BST

DSA Typescript

if (node === null) return true;

Single node tree

Returns true because one node always satisfies BST rules

DSA Typescript

if (node === null) return true;

Tree with duplicate values

Returns false because BST requires strictly less or greater values

DSA Typescript

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

When to Use This Pattern

When you need to check if a binary tree follows the BST rules, use range limits on nodes during recursion to verify each node fits the BST property.

Common Mistakes

Mistake: Only checking immediate children instead of all descendants for BST property
Fix: Use min and max range parameters to ensure all descendants fit BST rules, not just direct children

Mistake: Allowing equal values on left or right subtree
Fix: Use strict inequality (node.val <= min or node.val >= max) to disallow duplicates

Summary

Checks if a binary tree is a valid binary search tree by verifying node value ranges.

Use when you want to confirm a tree maintains BST ordering rules.

The key insight is to track allowed min and max values for each node during recursion.