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.

Practice

1. What does it mean for a binary tree to be a Binary Search Tree (BST)?

easy

A. All nodes have the same value.

B. Every node has exactly two children.

C. The tree is balanced with equal height on both sides.

D. Every node's left subtree contains values less than the node, and right subtree contains values greater.

Solution

1. Step 1: Understand BST property

   A BST requires that for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

2. Step 2: Compare options with definition

   Every node's left subtree contains values less than the node, and right subtree contains values greater. matches the BST property exactly, while others describe different tree properties.

3. Final Answer:

   Every node's left subtree contains values less than the node, and right subtree contains values greater. -> Option D

4. Quick Check:

   BST property = Every node's left subtree contains values less than the node, and right subtree contains values greater. [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 Go function signature correctly represents a function to check if a binary tree is a BST?

easy

A. func isBST(root *Node) bool

B. func isBST(root Node) int

C. func checkBST(root *Node) string

D. func validateBST(root Node) void

Solution

1. Step 1: Identify correct parameter and return types

   The function should accept a pointer to the root node (to avoid copying) and return a boolean indicating if the tree is BST.

2. Step 2: Match with options

   func isBST(root *Node) bool matches this: it takes *Node and returns bool. Others have wrong parameter types or return types.

3. Final Answer:

   func isBST(root *Node) bool -> Option A

4. Quick Check:

   Pointer input + bool output = func isBST(root *Node) bool [OK]

Hint: Use pointer receiver and bool return for BST check [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Returning int or string instead of bool
• Using void (no return) for validation function

3. Given the following Go code, what will be the output?

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func isBSTUtil(node *Node, min, max int) bool {
    if node == nil {
        return true
    }
    if node.Val <= min || node.Val >= max {
        return false
    }
    return isBSTUtil(node.Left, min, node.Val) && isBSTUtil(node.Right, node.Val, max)
}

func isBST(root *Node) bool {
    return isBSTUtil(root, -1000, 1000)
}

func main() {
    root := &Node{Val: 10}
    root.Left = &Node{Val: 5}
    root.Right = &Node{Val: 15}
    root.Right.Left = &Node{Val: 6}
    root.Right.Right = &Node{Val: 20}
    fmt.Println(isBST(root))
}

medium

A. false

B. true

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace tree values against BST rules

   The node with value 6 is in the right subtree of 10 but less than 10, violating BST property.

2. Step 2: Check isBSTUtil logic

   isBSTUtil checks if node.Val is within (min, max). For node 6, min=10, max=15, but 6 <= 10 fails the condition, returning false.

3. Final Answer:

   false -> Option A

4. Quick Check:

   6 in right subtree < 10 = false [OK]

Hint: Check subtree values against min/max bounds [OK]

Common Mistakes:

• Ignoring subtree value constraints
• Assuming all nodes in right subtree are greater than root only
• Not updating min/max bounds during recursion

4. The following Go function is intended to check if a binary tree is a BST, but it has a bug. What is the bug?

func isBST(node *Node) bool {
    if node == nil {
        return true
    }
    if node.Left != nil && node.Left.Val > node.Val {
        return false
    }
    if node.Right != nil && node.Right.Val < node.Val {
        return false
    }
    return isBST(node.Left) && isBST(node.Right)
}

medium

A. It does not handle nil nodes correctly.

B. It only compares immediate children, missing deeper subtree violations.

C. It uses wrong comparison operators for BST.

D. It causes infinite recursion.

Solution

1. Step 1: Analyze comparison logic

   The function compares only node.Left.Val and node.Right.Val with node.Val, ignoring entire subtree values.

2. Step 2: Understand BST violation cases

   A violation can occur deeper in subtrees, e.g., a left subtree node greater than root, which this function misses.

3. Final Answer:

   It only compares immediate children, missing deeper subtree violations. -> Option B

4. Quick Check:

   Check all subtree nodes, not just immediate children [OK]

Hint: Check entire subtree ranges, not just direct children [OK]

Common Mistakes:

• Checking only immediate children values
• Not passing min/max bounds in recursion
• Assuming local checks guarantee global BST

5. You want to validate if a binary tree is a BST but the tree nodes can have duplicate values. Which modification to the standard BST validation logic is correct to allow duplicates only on the right subtree?

hard

A. Change the condition to allow node.Val <= max for left subtree and node.Val > max for right subtree.

B. Allow duplicates only if node.Val >= min for left subtree and node.Val < max for right subtree.

C. Allow duplicates only if node.Val > min for left subtree and node.Val <= max for right subtree.

D. Allow duplicates on both sides without changing conditions.

Solution

1. Step 1: Understand duplicate placement in BST

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

2. Step 2: Adjust min/max conditions accordingly

   Change violation check to (node.Val <= min || node.Val > max), enforcing node.Val > min && node.Val <= max. This allows equality to max (parent.Val in right calls) but enforces > min (parent.Val in left calls).

3. Final Answer:

   Allow duplicates only if node.Val > min for left subtree and node.Val <= max for right subtree. -> Option C

4. Quick Check:

   > min && <= max = duplicates on right only [OK]

Hint: Use > min && <= max to allow duplicates on right [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Not adjusting inequality signs properly
• Allowing duplicates on both sides without rules