Validate if Tree is BST in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Validation on a Simple Tree

What is the output of the following Go code that checks if a binary tree is a BST?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isBST(root *TreeNode, min, max *int) bool {
    if root == nil {
        return true
    }
    if (min != nil && root.Val <= *min) || (max != nil && root.Val >= *max) {
        return false
    }
    return isBST(root.Left, min, &root.Val) && isBST(root.Right, &root.Val, max)
}

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

A false

B true

C Compilation error

D panic: runtime error

💡 Hint

Check if all nodes in the right subtree are greater than the root.

The tree is not a BST because the node with value 6 is in the right subtree of 10 but less than 10.

The function returns false.

❓ Predict Output

intermediate

Output of BST Validation on a Perfect BST

What does the following Go code print when checking if the tree is a BST?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isBST(root *TreeNode, min, max *int) bool {
    if root == nil {
        return true
    }
    if (min != nil && root.Val <= *min) || (max != nil && root.Val >= *max) {
        return false
    }
    return isBST(root.Left, min, &root.Val) && isBST(root.Right, &root.Val, max)
}

func main() {
    root := &TreeNode{Val: 8}
    root.Left = &TreeNode{Val: 3}
    root.Right = &TreeNode{Val: 10}
    root.Left.Left = &TreeNode{Val: 1}
    root.Left.Right = &TreeNode{Val: 6}
    root.Right.Right = &TreeNode{Val: 14}
    fmt.Println(isBST(root, nil, nil))
}

A false

B Compilation error

C true

D panic: runtime error

💡 Hint

All left children are less and right children are greater than their parent nodes.

The tree satisfies BST properties at every node.

The function returns true.

🔧 Debug

advanced

Identify the Bug in BST Validation Code

What error will the following Go code produce when run?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

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

func main() {
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 7}
    fmt.Println(isBST(root, -2147483648, 2147483647))
}

A Compilation error: cannot use int for min/max pointers

B false

C panic: nil pointer dereference

D true

💡 Hint

Check how min and max are passed and used.

The code uses int values instead of pointers for min and max, which works correctly here.

The tree is a valid BST, so it returns true.

🧠 Conceptual

advanced

Why Use Min and Max Pointers in BST Validation?

Why do some BST validation functions use pointers for min and max values instead of plain integers?

A To improve performance by avoiding copying integers

B To allow nil values representing no boundary constraints at the start

C Because Go does not support passing integers by value

D To enable concurrent access to min and max values

💡 Hint

Think about how to represent the absence of a limit.

Using pointers allows passing nil to represent no minimum or maximum boundary at the root.

🚀 Application

expert

Count Nodes Violating BST Property

Given the following tree, how many nodes violate the BST property?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func countViolations(root *TreeNode, min, max *int) int {
    if root == nil {
        return 0
    }
    count := 0
    if (min != nil && root.Val <= *min) || (max != nil && root.Val >= *max) {
        count = 1
    }
    count += countViolations(root.Left, min, &root.Val)
    count += countViolations(root.Right, &root.Val, max)
    return count
}

func main() {
    root := &TreeNode{Val: 10}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 15}
    root.Left.Left = &TreeNode{Val: 1}
    root.Left.Right = &TreeNode{Val: 12}
    root.Right.Left = &TreeNode{Val: 6}
    root.Right.Right = &TreeNode{Val: 20}
    fmt.Println(countViolations(root, nil, nil))
}

A 3

B 2

C 1

D 4

💡 Hint

Check each node if it violates min/max constraints during traversal.

Nodes with values 12, 6, and 15 violate BST properties in their positions.

So total violations are 3.

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