Validate if Tree is BST in DSA Javascript - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check node value within allowed range?

Yes↓

Recurse left subtree with updated max bound

↓

Recurse right subtree with updated min bound

↓

If all nodes valid, return True

↓

Else return False

Start from the root, check if each node's value fits the BST rules within allowed min and max bounds, recursively check left and right subtrees.

Execution Sample

DSA Javascript

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 are within valid min and max bounds recursively.

Execution Table

Step	Operation	Node Visited	Allowed Range (min, max)	Result	Tree State
1	Start at root	10	(-∞, ∞)	Check 10 in range	10 / \ 5 15
2	Recurse left	5	(-∞, 10)	Check 5 in range	10 / \ 5 15
3	Recurse left.left	3	(-∞, 5)	Check 3 in range	10 / \ 5 15 / 3
4	Recurse left.left.left	null	(-∞, 3)	Null node, return true	No change
5	Recurse left.left.right	null	(3, 5)	Null node, return true	No change
6	Back to 5, recurse right	7	(5, 10)	Check 7 in range	10 / \ 5 15 / \ 3 7
7	Recurse right.left	null	(5, 7)	Null node, return true	No change
8	Recurse right.right	null	(7, 10)	Null node, return true	No change
9	Back to root, recurse right	15	(10, ∞)	Check 15 in range	10 / \ 5 15 / \ 3 7
10	Recurse right.left	13	(10, 15)	Check 13 in range	10 / \ 5 15 / \ / 3 7 13
11	Recurse right.left.left	null	(10, 13)	Null node, return true	No change
12	Recurse right.left.right	null	(13, 15)	Null node, return true	No change
13	Recurse right.right	20	(15, ∞)	Check 20 in range	10 / \ 5 15 / \ / \ 3 7 13 20
14	Recurse right.right.left	null	(15, 20)	Null node, return true	No change
15	Recurse right.right.right	null	(20, ∞)	Null node, return true	No change
16	All nodes valid	N/A	N/A	Return true	Tree is BST

💡 All nodes satisfy BST property within their allowed ranges, so the tree is a valid BST.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 9	After Step 13	Final
node.val	10	5	7	15	20	N/A
min	-∞	-∞	5	10	15	N/A
max	∞	10	10	∞	∞	N/A
Return value	N/A	true	true	true	true	true

Key Moments - 3 Insights

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

Because in a BST, all left subtree nodes must be less than the current node, so max is current node's value; all right subtree nodes must be greater, so min is current node's value. See steps 2 and 9 in execution_table.

What happens when we reach a null node?

A null node means leaf's child, which is valid by default, so we return true. See steps 4, 5, 7, 8, 11, 12, 14, 15.

Why do we check node.val <= min or node.val >= max instead of just equality?

Because BST requires strictly less or greater values, duplicates are not allowed on either side. This ensures strict ordering. See step 3 where node.val is checked against min and max.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the allowed range for node 7?

A (5, 10)

B (-∞, 10)

C (5, 7)

D (7, 10)

💡 Hint

Check the 'Allowed Range' column at step 6 in execution_table.

At which step does the recursion check the right child of node 15?

A Step 10

B Step 9

C Step 13

D Step 16

💡 Hint

Look for 'Recurse right.right' operation in execution_table.

If node 13 had value 16, which step would fail the BST check?

A Step 10

B Step 13

C Step 6

D Step 2

💡 Hint

Check the allowed range for node 13 at step 10 and what happens at step 13.

Concept Snapshot

Validate BST by checking each node's value is strictly between min and max bounds.
Start at root with (-∞, ∞).
Recurse left with max = node.val.
Recurse right with min = node.val.
Return false if any node violates bounds.
Return true if all nodes valid.

Full Transcript

To check if a binary tree is a BST, we start at the root node and verify if its value lies within an allowed range, initially from negative infinity to positive infinity. For each node, we recursively check the left subtree with an updated maximum bound equal to the current node's value, and the right subtree with an updated minimum bound equal to the current node's value. If any node's value is not strictly within these bounds, the tree is not a BST. Null nodes are considered valid leaves. This process continues until all nodes are validated or a violation is found. The example tree with nodes 10, 5, 15, 3, 7, 13, and 20 passes all checks and is a valid BST.

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