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.

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