Validate if Tree is BST in DSA Go - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check left subtree values < current node?

↓

Recursively validate left subtree

↓

Check right subtree values > current node?

↓

Recursively validate right subtree

↓

If all checks pass, return True

↓

Else return False

We start at the root and recursively check if all nodes in the left subtree are smaller and all nodes in the right subtree are larger, ensuring BST properties hold.

Execution Sample

DSA Go

func isBST(node *Node, min, max int) bool {
  if node == nil {
    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 ensuring each node's value is within valid min and max bounds.

Execution Table

Step	Operation	Node Visited	Min Bound	Max Bound	Result	Tree State
1	Start at root	10	-∞	+∞	Check node 10	10 / \ 5 15
2	Check left subtree	5	-∞	10	Check node 5	10 / \ 5 15
3	Check left of 5	3	-∞	5	Check node 3	10 / \ 5 15 / 3
4	Left of 3 is nil	nil	-∞	3	True	No change
5	Right of 3 is nil	nil	3	5	True	No change
6	Left subtree of 5 valid	5	-∞	10	True	No change
7	Check right subtree	7	5	10	Check node 7	10 / \ 5 15 \ 7
8	Left of 7 is nil	nil	5	7	True	No change
9	Right of 7 is nil	nil	7	10	True	No change
10	Right subtree of 5 valid	7	5	10	True	No change
11	Left subtree of 10 valid	5	-∞	10	True	No change
12	Check right subtree	15	10	+∞	Check node 15	10 / \ 5 15
13	Left of 15 is nil	nil	10	15	True	No change
14	Right of 15 is nil	nil	15	+∞	True	No change
15	Right subtree of 10 valid	15	10	+∞	True	No change
16	All checks passed	10	-∞	+∞	True	Tree is BST

💡 All nodes satisfy BST property within min and max bounds, so tree is BST

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 11	After Step 16
node	10 (root)	5 (left child)	5 (left child)	10 (root)	10 (root)
min	-∞	-∞	-∞	-∞	-∞
max	+∞	10	10	+∞	+∞
result	N/A	Checking	True	True	True

Key Moments - 3 Insights

Why do we pass min and max bounds when checking each node?

Because each node must be greater than all nodes in its left subtree (min bound) and less than all nodes in its right subtree (max bound). This is shown in execution_table steps 3, 7, and 12 where bounds narrow.

What happens when we reach a nil (empty) node?

We return True immediately because an empty subtree is always valid. This is shown in steps 4, 5, 8, 9, 13, and 14.

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

To ensure the current node's value fits strictly between allowed bounds. If it doesn't, we return False immediately, stopping further checks. This is the core BST validation condition.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what are the min and max bounds for node 3?

A -∞ and 5

B -∞ and 10

C 5 and 10

D 3 and 5

💡 Hint

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

At which step does the function confirm the left subtree of node 5 is valid?

A Step 4

B Step 6

C Step 9

D Step 11

💡 Hint

Look for the row where 'Left subtree of 5 valid' is noted in the 'Operation' column

If node 7 had value 11 instead, which step would fail the BST check?

A Step 7

B Step 10

C Step 12

D Step 16

💡 Hint

Check the 'Result' column at step 10 where node 7 is validated against bounds 5 and 10

Concept Snapshot

Validate BST by recursively checking each node's value is > min and < max bounds.
Pass updated bounds down the tree.
Return true if all nodes satisfy conditions.
Return false immediately if any node violates bounds.
Nil nodes are valid by default.
Use recursion with min/max parameters.

Full Transcript

To check if a binary tree is a BST, we start at the root node and recursively verify that all nodes in the left subtree have values less than the current node, and all nodes in the right subtree have values greater than the current node. We keep track of minimum and maximum allowed values for each node. If a node's value is outside these bounds, we return false immediately. If we reach a nil node, we return true because an empty subtree is valid. This process continues until all nodes are checked or a violation is found. The example tree with root 10, left child 5, and right child 15 passes all checks, confirming it is a BST.