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.