BST Property and Why It Matters in DSA Go - Build from Scratch

BST Property and Why It Matters

📖 Scenario: Imagine you are organizing a library's book collection. Each book has a unique ID number. You want to store these books so you can quickly find any book by its ID. A Binary Search Tree (BST) helps you do this by keeping books in order.

🎯 Goal: You will build a simple Binary Search Tree (BST) with a few book IDs. Then, you will check if the tree follows the BST property: for every node, all book IDs in the left subtree are smaller, and all in the right subtree are larger. Finally, you will print the tree's in-order traversal to see the sorted order of book IDs.

📋 What You'll Learn

Create a BST node structure with integer book ID

Insert given book IDs into the BST following BST rules

Write a function to check if the tree satisfies the BST property

Print the in-order traversal of the BST

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to organize data for fast searching, insertion, and deletion.

💼 Career

Understanding BSTs is essential for software engineers working with data storage, search algorithms, and system design.

1

Create BST Node Structure and Insert Books

Create a struct called Node with an integer field bookID and two pointers left and right to Node. Then create a function insert that takes a pointer to Node and an integer bookID, and inserts the book ID into the BST following the BST rules. Finally, create a variable root of type *Node and insert these book IDs in order: 50, 30, 70, 20, 40, 60, 80.

DSA Go

// Define Node struct and insert function
// Create root and insert book IDs 50, 30, 70, 20, 40, 60, 80
// Your code here

Hint

Define the Node struct with bookID, left, and right. The insert function should add nodes recursively following BST rules.

2

Add Function to Check BST Property

Create a function isBST that takes a pointer to Node and two integers min and max. It returns true if the subtree rooted at the node satisfies the BST property: all bookID values are strictly between min and max. Use isBST recursively to check left and right subtrees with updated ranges. Call isBST(root, -1, 101) and store the result in a variable validBST.

DSA Go

package main

import "fmt"

// Add isBST function here

func main() {
    var root *Node
    root = insert(root, 50)
    root = insert(root, 30)
    root = insert(root, 70)
    root = insert(root, 20)
    root = insert(root, 40)
    root = insert(root, 60)
    root = insert(root, 80)

    // Call isBST and store result in validBST
    // Your code here
}

Hint

Use recursion to check if each node's bookID is between min and max. Update min and max when checking left and right children.

3

Write In-Order Traversal Function

Create a function inOrder that takes a pointer to Node and prints the bookID values in ascending order separated by spaces. Use recursion to first visit the left subtree, then print the current node's bookID, then visit the right subtree.

DSA Go

package main

import "fmt"

// Add inOrder function here

func main() {
    var root *Node
    root = insert(root, 50)
    root = insert(root, 30)
    root = insert(root, 70)
    root = insert(root, 20)
    root = insert(root, 40)
    root = insert(root, 60)
    root = insert(root, 80)

    validBST := isBST(root, -1, 101)

    // Call inOrder to print book IDs
    // Your code here
}

Hint

Use recursion to print left subtree, then current node's bookID, then right subtree.

4

Print BST Validity Result

Print "BST Valid: " followed by the value of validBST on a new line.

DSA Go

package main

import "fmt"

func main() {
    // Previous code here

    // Print BST validity
    // Your code here
}

Hint

Use fmt.Printf("BST Valid: %t\n", validBST) to print the boolean result.