Validate if Tree is BST in DSA Typescript - Build from Scratch

Validate if Tree is BST

📖 Scenario: You are working with a simple tree structure used in a small app to store numbers. You want to check if this tree follows the rules of a Binary Search Tree (BST).A BST is a tree where for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

🎯 Goal: Build a TypeScript program that creates a tree, sets up helper variables, writes a function to check if the tree is a BST, and prints the result.

📋 What You'll Learn

Create a tree using a Node class with value, left, and right properties

Add a helper function to check if the tree is a BST

Use recursion to validate BST properties

Print true if the tree is a BST, otherwise false

💡 Why This Matters

🌍 Real World

Binary Search Trees are used in databases and search engines to quickly find data.

💼 Career

Understanding BST validation helps in roles involving data structures, algorithms, and software development.

1

Create the Tree Structure

Create a class called Node with a constructor that takes a value (number), and optional left and right nodes. Then create a tree variable called root with this exact structure:
root = new Node(10, new Node(5), new Node(15))

DSA Typescript

// Define Node class and create root node
// Your code here

Hint

Think of Node as a box holding a number and links to left and right boxes.

2

Add Helper Variables for Limits

Create two variables called minValue and maxValue and set them to Number.NEGATIVE_INFINITY and Number.POSITIVE_INFINITY respectively. These will help check the valid range for node values.

DSA Typescript

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number, left: Node | null = null, right: Node | null = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

const root = new Node(10, new Node(5), new Node(15));

// Create minValue and maxValue variables
// Your code here

Hint

Use JavaScript's built-in Number.NEGATIVE_INFINITY and Number.POSITIVE_INFINITY for limits.

3

Write the BST Validation Function

Write a function called isBST that takes a node (Node or null), a min number, and a max number. It returns true if the subtree rooted at node is a BST within the range min to max. Use recursion to check left and right subtrees with updated ranges.

DSA Typescript

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number, left: Node | null = null, right: Node | null = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

const root = new Node(10, new Node(5), new Node(15));

const minValue = Number.NEGATIVE_INFINITY;
const maxValue = Number.POSITIVE_INFINITY;

// Write isBST function below
// Your code here

Hint

Check if current node's value is between min and max. Then check left subtree with updated max, and right subtree with updated min.

4

Print if the Tree is a BST

Use console.log to print the result of calling isBST with root, minValue, and maxValue.

DSA Typescript

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number, left: Node | null = null, right: Node | null = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

const root = new Node(10, new Node(5), new Node(15));

const minValue = Number.NEGATIVE_INFINITY;
const maxValue = Number.POSITIVE_INFINITY;

function isBST(node: Node | null, min: number, max: number): boolean {
    if (node === null) {
        return true;
    }
    if (node.value = max) {
        return false;
    }
    return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}

// Print the result of isBST
// Your code here

Hint

Call console.log(isBST(root, minValue, maxValue)) to see if the tree is a BST.