Validate if Tree is BST in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Validation Function

What is the output of the following TypeScript function when called with the given tree?

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, min: number = -Infinity, max: number = Infinity): boolean {
  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);
}

// Tree structure:
//      5
//     / \
//    3   7
//   / \   \
//  2   4   8

const tree = new TreeNode(5,
  new TreeNode(3, new TreeNode(2), new TreeNode(4)),
  new TreeNode(7, null, new TreeNode(8))
);

console.log(isValidBST(tree));

A true

B false

C SyntaxError

D TypeError

💡 Hint

Check if all nodes follow the BST property: left < root < right.

The function checks recursively if each node's value is within the allowed min and max range. The given tree satisfies BST properties, so the output is true.

❓ Predict Output

intermediate

Output for Invalid BST Tree

What is the output of the isValidBST function for the following tree?

DSA Typescript

// Tree structure:
//      5
//     / \
//    3   7
//   / \   \
//  2   6   8

const invalidTree = new TreeNode(5,
  new TreeNode(3, new TreeNode(2), new TreeNode(6)),
  new TreeNode(7, null, new TreeNode(8))
);

console.log(isValidBST(invalidTree));

A false

B true

C ReferenceError

D RangeError

💡 Hint

Check if the left subtree contains values greater than root.

The node with value 6 is in the left subtree of 5 but is greater than 5, violating BST rules. So the function returns false.

🔧 Debug

advanced

Identify the Error in BST Validation Code

What error will the following code produce when run?

DSA Typescript

function isValidBST(root: TreeNode | null): boolean {
  if (!root) return true;
  if (root.left && root.left.val >= root.val) return false;
  if (root.right && root.right.val <= root.val) return false;
  return isValidBST(root.left) && isValidBST(root.right);
}

// Tree:
//      10
//     /  \
//    5    15
//        /  \
//       6    20

const tree = new TreeNode(10,
  new TreeNode(5),
  new TreeNode(15, new TreeNode(6), new TreeNode(20))
);

console.log(isValidBST(tree));

A false

B No error, outputs true

C StackOverflowError

D true

💡 Hint

Check if the function correctly validates all BST rules beyond immediate children.

The function only checks immediate children values, missing deeper violations. The node with value 6 is in the right subtree of 10 but less than 10, so the tree is not a BST. The function returns true.

🧠 Conceptual

advanced

Why Use Min and Max in BST Validation?

Why does the isValidBST function use min and max parameters during recursion?

A To store the sum of all node values in the tree.

B To count the number of nodes visited during traversal.

C To keep track of the allowed value range for each node to ensure BST property is maintained.

D To balance the tree by adjusting node values.

💡 Hint

Think about how BST property restricts node values relative to ancestors.

The min and max parameters define the valid range for each node's value based on its ancestors, ensuring the entire subtree respects BST rules, not just immediate children.

🚀 Application

expert

Count Valid BST Subtrees in a Binary Tree

Given a binary tree, how many subtrees are valid BSTs? Consider each node as root of a subtree. Use the isValidBST function to check each subtree.

DSA Typescript

function countBSTSubtrees(root: TreeNode | null): number {
  if (!root) return 0;
  let count = 0;
  if (isValidBST(root)) count++;
  count += countBSTSubtrees(root.left);
  count += countBSTSubtrees(root.right);
  return count;
}

// Tree:
//      10
//     /  \
//    5    15
//        /  \
//       6    20

const tree = new TreeNode(10,
  new TreeNode(5),
  new TreeNode(15, new TreeNode(6), new TreeNode(20))
);

console.log(countBSTSubtrees(tree));

A 3

B 2

C 5

D 4

💡 Hint

Check each subtree rooted at every node and count how many are valid BSTs.

The valid BST subtrees are rooted at 5, 15 (6 < 15 < 20), 6, and 20. The whole tree is invalid. Total valid BST subtrees: 4.

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. The tree is balanced with equal height on both sides

C. All nodes have the same value

D. Every node's left subtree has smaller values and right subtree has larger values

Solution

1. Step 1: Understand BST property

   A BST requires that for each node, all values in the left subtree are smaller and all values in the right subtree are larger.

2. Step 2: Compare options with definition

   Every node's left subtree has smaller values and right subtree has larger values matches the BST property exactly, while others describe different tree properties.

3. Final Answer:

   Every node's left subtree has smaller values and right subtree has larger values -> Option D

4. Quick Check:

   BST property = Every node's left subtree has smaller values and right subtree has larger values [OK]

Hint: Remember BST means left < node < right for all nodes [OK]

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Assuming all values are equal

2. Which TypeScript function signature correctly represents a function to check if a binary tree is a BST?

easy

A. function isBST(root: any): void

B. function isBST(root: TreeNode | null): boolean

C. function isBST(root: TreeNode): number

D. function isBST(root: number): boolean

Solution

1. Step 1: Identify correct parameter and return types

   The function should accept a tree node or null and return a boolean indicating if it is a BST.

2. Step 2: Match options with correct signature

   function isBST(root: TreeNode | null): boolean matches this: input is TreeNode or null, output is boolean. Others have wrong types or return types.

3. Final Answer:

   function isBST(root: TreeNode | null): boolean -> Option B

4. Quick Check:

   Correct signature = function isBST(root: TreeNode | null): boolean [OK]

Hint: Input is root node or null, output is true/false [OK]

Common Mistakes:

• Using wrong parameter type like number
• Returning number instead of boolean
• Using void return type

3. What will be the output of the following TypeScript code snippet?

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

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

const tree = new TreeNode(10, new TreeNode(5), new TreeNode(15, new TreeNode(6), new TreeNode(20)));
console.log(isBST(tree));

medium

A. SyntaxError

B. true

C. false

D. RuntimeError

Solution

1. Step 1: Analyze the tree structure

   The 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 in right subtree of 10 but less than 10, violating BST property. So function returns false.

3. Final Answer:

   false -> Option C

4. Quick Check:

   6 in right subtree < 10 = false [OK]

Hint: Check if left < node < right recursively [OK]

Common Mistakes:

• Ignoring min/max constraints in recursion
• Assuming all subtrees are BST without checks
• Confusing node values in subtrees

4. Identify the bug in this TypeScript function to check if a tree is BST:

function isBST(root: TreeNode | null): boolean {
  if (!root) return true;
  if (root.left && root.left.val > root.val) return false;
  if (root.right && root.right.val < root.val) return false;
  return isBST(root.left) && isBST(root.right);
}

medium

A. It does not check the entire subtree values against min/max limits

B. It uses wrong comparison operators for left and right children

C. It returns true for null nodes incorrectly

D. It does not handle empty tree input

Solution

1. Step 1: Understand the function checks

   The function only compares immediate children values with current node, not entire subtree ranges.

2. Step 2: Explain why this is a bug

   BST requires all nodes in left subtree < current node and all in right subtree > current node, not just direct children.

3. Final Answer:

   It does not check the entire subtree values against min/max limits -> Option A

4. Quick Check:

   Missing min/max range check = It does not check the entire subtree values against min/max limits [OK]

Hint: Check full subtree ranges, not just immediate children [OK]

Common Mistakes:

• Only comparing direct children values
• Ignoring recursive min/max constraints
• Assuming null nodes cause errors

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 root.val <= min in the validation function:

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

hard

A. Change to root.val < min to allow duplicates on right

B. Change to root.val <= min and root.val < max

C. Change to root.val < min and root.val <= max

D. Change to root.val <= min and root.val <= max

Solution

1. Step 1: Understand duplicates on right subtree rule

   Duplicates allowed only on right means left subtree nodes must be strictly less than current node, right subtree nodes greater than or equal.

2. Step 2: Adjust min/max comparisons accordingly

   Replace root.val <= min with root.val < min. This fails only if strictly less than min (allows equal to min on right recursion), keeping root.val >= max for strict upper bound.

3. Final Answer:

   Change to root.val < min to allow duplicates on right -> Option A

4. Quick Check:

   Duplicates right subtree = Change to root.val < min [OK]

Hint: Use strict less on left, less or equal on right for duplicates [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Using <= on both sides
• Not changing min/max checks