Validate if Tree is BST in DSA Typescript - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check if node is null?

Yes→Return True

No↓

Check node value > min and < max?

No→Return False

Yes↓

Recurse left subtree with updated max = node value

↓

Recurse right subtree with updated min = node value

↓

Return left_result AND right_result

We start at the root and check if each node's value fits within allowed min and max limits, updating these limits as we go down left and right subtrees.

Execution Sample

DSA Typescript

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);
}

This function checks if a binary tree is a BST by verifying node values against min and max bounds recursively.

Execution Table

Step	Operation	Node Visited	Min Bound	Max Bound	Result	Tree State
1	Start at root	10	-Infinity	Infinity	Continue	10 / \ 5 15
2	Check node 10 value	10	-Infinity	Infinity	10 > -∞ and < ∞: True	10 / \ 5 15
3	Recurse left subtree	5	-Infinity	10	Continue	10 / \ 5 15
4	Check node 5 value	5	-Infinity	10	5 > -∞ and < 10: True	10 / \ 5 15
5	Recurse left subtree	2	-Infinity	5	Continue	10 / \ 5 15 / 2
6	Check node 2 value	2	-Infinity	5	2 > -∞ and < 5: True	10 / \ 5 15 / 2
7	Recurse left subtree	null	-Infinity	2	True (null node)	10 / \ 5 15 / 2
8	Recurse right subtree	null	2	5	True (null node)	10 / \ 5 15 / 2
9	Left subtree of 5 is BST	5	-Infinity	10	True	10 / \ 5 15 / 2
10	Recurse right subtree	7	5	10	Continue	10 / \ 5 15 / \ 2 7
11	Check node 7 value	7	5	10	7 > 5 and < 10: True	10 / \ 5 15 / \ 2 7
12	Recurse left subtree	null	5	7	True (null node)	10 / \ 5 15 / \ 2 7
13	Recurse right subtree	null	7	10	True (null node)	10 / \ 5 15 / \ 2 7
14	Right subtree of 5 is BST	5	-Infinity	10	True	10 / \ 5 15 / \ 2 7
15	Left subtree of 10 is BST	10	-Infinity	Infinity	True	10 / \ 5 15 / \ 2 7
16	Recurse right subtree	15	10	Infinity	Continue	10 / \ 5 15 / \ 2 7 20
17	Check node 15 value	15	10	Infinity	15 > 10 and < ∞: True	10 / \ 5 15 / \ 2 7 20
18	Recurse left subtree	null	10	15	True (null node)	10 / \ 5 15 / \ 2 7 20
19	Recurse right subtree	20	15	Infinity	Continue	10 / \ 5 15 / \ 2 7 20
20	Check node 20 value	20	15	Infinity	20 > 15 and < ∞: True	10 / \ 5 15 / \ 2 7 20
21	Recurse left subtree	null	15	20	True (null node)	10 / \ 5 15 / \ 2 7 20
22	Recurse right subtree	null	20	Infinity	True (null node)	10 / \ 5 15 / \ 2 7 20
23	Right subtree of 15 is BST	15	10	Infinity	True	10 / \ 5 15 / \ 2 7 20
24	Right subtree of 10 is BST	10	-Infinity	Infinity	True	10 / \ 5 15 / \ 2 7 20
25	Final result	root	-Infinity	Infinity	True (Tree is BST)	10 / \ 5 15 / \ 2 7 20

💡 All nodes satisfy BST conditions; recursion ends with True.

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 15	After Step 24	Final
node	10 (root)	5 (left child)	5 (left child)	10 (root)	15 (right child)	10 (root)
min	-Infinity	-Infinity	-Infinity	-Infinity	10	-Infinity
max	Infinity	10	10	Infinity	Infinity	Infinity
result	N/A	Continue	True (left subtree BST)	True (left subtree BST)	True (right subtree BST)	True (whole tree BST)

Key Moments - 3 Insights

Why do we update max when going left and min when going right?

Because left subtree nodes must be less than the current node (max updated to node.val), and right subtree nodes must be greater (min updated to node.val). See execution_table steps 3 and 16.

What happens when we reach a null node?

We return True because an empty subtree is always a valid BST. This is shown in steps 7, 8, 12, 13, 18, 21, and 22.

Why do we check node.val <= min or >= max to return False?

Because if node value is not strictly between min and max, it violates BST rules. This check ensures no duplicates or invalid placements. See step 2 for the condition.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the min and max bounds for node 7?

A min = 7, max = 10

B min = 5, max = 10

C min = -Infinity, max = 5

D min = 10, max = Infinity

💡 Hint

Check the 'Min Bound' and 'Max Bound' columns at step 10 in execution_table.

At which step does the recursion confirm the left subtree of node 5 is a BST?

A Step 9

B Step 14

C Step 15

D Step 24

💡 Hint

Look for the row where 'Left subtree of 5 is BST' is mentioned in the 'Operation' column.

If node 7 had value 11, what would happen in the execution_table?

A Step 10 min and max bounds would change

B Step 11 would continue as normal

C Step 11 would return False because 11 is not < 10

D The tree would still be a BST

💡 Hint

Check the condition at step 11 where node value must be between min and max.

Concept Snapshot

Validate if Tree is BST:
- Start at root with min = -∞, max = ∞
- For each node, check if min < node.val < max
- Recurse left with max = node.val
- Recurse right with min = node.val
- Return True if all nodes satisfy conditions
- Return False immediately if violation found

Full Transcript

To check if a binary tree is a BST, we start at the root node with minimum and maximum bounds set to negative and positive infinity. For each node, we verify if its value is strictly greater than the min bound and less than the max bound. We then recursively check the left subtree, updating the max bound to the current node's value, and the right subtree, updating the min bound to the current node's value. If any node violates these bounds, we return false immediately. If we reach a null node, we return true since an empty subtree is valid. The process continues until all nodes are validated, confirming if the tree is a BST or not.

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