BST Search Operation in DSA Go - Build from Scratch

BST Search Operation

📖 Scenario: You are building a simple phone book application that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number. You want to find if a contact with a specific phone number exists in your phone book.

🎯 Goal: Build a program that creates a BST with given phone numbers, sets a target phone number to search for, implements the search operation in the BST, and prints whether the phone number is found or not.

📋 What You'll Learn

Create a BST node structure with integer phone number values

Insert given phone numbers into the BST

Create a variable for the target phone number to search

Implement a function to search the BST for the target phone number

Print the search result as 'Found' or 'Not Found'

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and databases often use BSTs to store and quickly search for unique keys like phone numbers.

💼 Career

Understanding BST search is fundamental for software engineers working with data structures, databases, and performance optimization.

1

Create BST Node Structure and Insert Phone Numbers

Create a struct called Node with an int field phone and two pointers left and right of type *Node. Then create a function insert that takes a *Node and an int phone number and returns the root *Node after inserting the phone number in the BST. Insert these phone numbers in order: 5551234, 5555678, 5550000, 5559999, 5554321. Store the root node in a variable called root.

DSA Go

// Define Node struct and insert function
// Insert phone numbers 5551234, 5555678, 5550000, 5559999, 5554321 into BST
// Store root node in variable root

Hint

Define a struct with fields for phone number and left/right child pointers. Use recursion to insert nodes in BST order.

2

Set Target Phone Number to Search

Create an int variable called target and set it to 5554321.

DSA Go

    // Create target variable with value 5554321
    // Your code here
}

Hint

Use target := 5554321 to create and set the variable.

3

Implement BST Search Function

Write a function called search that takes a *Node called root and an int called target. It returns bool. The function should return true if target is found in the BST rooted at root, otherwise false. Use the BST property to decide whether to search left or right subtree or return true if found.

DSA Go

func search(root *Node, target int) bool {
    // Your code here
}

func main() {
    var root *Node
    root = insert(root, 5551234)
    root = insert(root, 5555678)
    root = insert(root, 5550000)
    root = insert(root, 5559999)
    root = insert(root, 5554321)
    target := 5554321
}

Hint

Use recursion and compare target with current node's phone number to decide the search path.

4

Print Search Result

Use fmt.Println to print "Found" if search(root, target) returns true, otherwise print "Not Found".

DSA Go

    // Print "Found" if search(root, target) is true, else print "Not Found"
    // Your code here
}

Hint

Use an if-else statement to print the correct message based on the search result.