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.