Validate if Tree is BST in DSA Go - Build from Scratch

Validate if Tree is BST

📖 Scenario: Imagine you have a family tree where each person has a unique number. You want to check if this tree follows special rules so that it is a Binary Search Tree (BST). In a BST, every left child has a smaller number than its parent, and every right child has a bigger number than its parent.

🎯 Goal: You will build a simple program in Go to check if a given tree is a BST or not. This helps in many computer tasks like searching quickly.

📋 What You'll Learn

Create a tree node structure called Node with value, left, and right fields

Create a sample tree with exact values and structure

Write a function isBST that checks if the tree is a BST

Print true or false based on the check

💡 Why This Matters

🌍 Real World

Checking if a tree is a BST is important in databases and search engines to keep data organized for fast searching.

💼 Career

Software developers and data engineers often need to verify tree structures for correctness and efficiency.

1

Create the Tree Node Structure and Sample Tree

Create a struct called Node with an int field value and two pointers to Node called left and right. Then create a variable root which is a pointer to Node representing this tree:

10
/ \
5 15
/ \ \
2 7 20

DSA Go

// Define Node struct and create root node with children
// Your code here

Hint

Use type Node struct to define the tree node. Use &Node{value: X} to create nodes and link them.

2

Add Helper Function Parameters for Limits

Create two variables min and max of type int in the main function. Set min to -1 << 31 (minimum int) and max to 1<<31 - 1 (maximum int). These will help check if values are in the correct range.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func main() {
    root := &Node{value: 10}
    root.left = &Node{value: 5}
    root.right = &Node{value: 15}
    root.left.left = &Node{value: 2}
    root.left.right = &Node{value: 7}
    root.right.right = &Node{value: 20}

    // Create min and max int variables
    // Your code here
}

Hint

Use bit shifting to get minimum and maximum 32-bit integer values.

3

Write the isBST Function

Write a function isBST that takes a pointer to Node, and two int parameters min and max. It returns bool. The function should:
- Return true if the node is nil.
- Return false if the node's value is not between min and max.
- Recursively check the left subtree with updated max as node.value - 1.
- Recursively check the right subtree with updated min as node.value + 1.
- Return true only if both subtrees are BSTs.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func isBST(node *Node, min int, max int) bool {
    // Your code here
}

func main() {
    root := &Node{value: 10}
    root.left = &Node{value: 5}
    root.right = &Node{value: 15}
    root.left.left = &Node{value: 2}
    root.left.right = &Node{value: 7}
    root.right.right = &Node{value: 20}

    min := -1 << 31
    max := 1<<31 - 1
}

Hint

Check for nil node first. Then check if value is out of range. Use recursion for left and right subtrees with updated limits.

4

Print the Result of isBST Check

In the main function, call isBST with root, min, and max. Print the returned boolean value.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func isBST(node *Node, min int, max int) bool {
    if node == nil {
        return true
    }
    if node.value  max {
        return false
    }
    return isBST(node.left, min, node.value-1) && isBST(node.right, node.value+1, max)
}

func main() {
    root := &Node{value: 10}
    root.left = &Node{value: 5}
    root.right = &Node{value: 15}
    root.left.left = &Node{value: 2}
    root.left.right = &Node{value: 7}
    root.right.right = &Node{value: 20}

    min := -1 << 31
    max := 1<<31 - 1

    // Print the result of isBST
    // Your code here
}

Hint

Use println(isBST(root, min, max)) to print the result.