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

Validate if Tree is BST

📖 Scenario: You are working with a simple binary tree structure in JavaScript. Your task is 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 program that creates a binary tree, sets up a helper function to check BST rules, and then prints whether the tree is a valid BST or not.

📋 What You'll Learn

Create a binary tree with exact nodes and values

Add a helper function to validate BST rules

Use recursion to check the tree

Print 'true' if the tree is a BST, otherwise 'false'

💡 Why This Matters

🌍 Real World

Checking if a tree is a BST is important in databases and search algorithms where data needs to be organized for fast lookup.

💼 Career

Understanding BST validation helps in roles like software development and data engineering where tree data structures are common.

1

Create the binary tree nodes

Create a class called Node with a constructor that takes value, left, and right. Then create a tree with root node value 10, left child 5, and right child 15. Assign the root node to a variable called root.

DSA Javascript

// Define Node class and create root node with left and right children
// Your code here

Hint

Start by defining a Node class with a constructor. Then create the root node with value 10, and its left and right children with values 5 and 15.

2

Add helper function to check BST validity

Create a function called isBST that takes a node, a min value, and a max value. Initialize min and max to -Infinity and Infinity respectively when first called. The function should return false if the node value is not between min and max. Otherwise, recursively check the left subtree with updated max and the right subtree with updated min. Return true if all checks pass.

DSA Javascript

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

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

// Define isBST function to check BST validity
// Your code here

Hint

Use recursion to check if each node's value fits between min and max. Update these limits as you go down the tree.

3

Call the helper function with the root node

Create a variable called result and assign it the value returned by calling isBST with the root node.

DSA Javascript

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

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

function isBST(node, min = -Infinity, max = Infinity) {
  if (node === null) return true;
  if (node.value = max) return false;
  return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}

// Assign result by calling isBST with root
// Your code here

Hint

Call isBST with the root node and store the answer in result.

4

Print the result

Print the value of the variable result using console.log.

DSA Javascript

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

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

function isBST(node, min = -Infinity, max = Infinity) {
  if (node === null) return true;
  if (node.value = max) return false;
  return isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
}

const result = isBST(root);

// Print the result
// Your code here

Hint

Use console.log(result) to show if the tree is a BST.