BST Insert Operation in DSA Go - Build from Scratch

BST Insert Operation

📖 Scenario: You are building a simple phone book application that stores phone numbers in a Binary Search Tree (BST) to keep them sorted for quick search and insertion.

🎯 Goal: Build a BST and insert phone numbers into it using the BST insert operation.

📋 What You'll Learn

Create a BST node struct with integer phone number and left/right child pointers

Create a root node variable initialized to nil

Write a function to insert a phone number into the BST

Insert multiple phone numbers using the insert function

Print the BST in-order to show sorted phone numbers

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and databases use BSTs to keep data sorted for fast insertion and search.

💼 Career

Understanding BST insertions is fundamental for software engineers working with data storage, search algorithms, and system design.

1

Create BST Node and Root

Create a struct called Node with an integer field phone and two pointers left and right of type *Node. Then create a variable called root of type *Node and set it to nil.

DSA Go

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

var root *Node = nil
// Your code here

Hint

Define the struct with the fields exactly as phone int, left *Node, and right *Node. Then declare root as a pointer to Node and set it to nil.

2

Create Insert Function

Create a function called insert that takes two parameters: node of type *Node and phone of type int. The function returns a *Node. This function inserts the phone into the BST rooted at node following BST insert rules.

DSA Go

package main

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

var root *Node = nil

func insert(node *Node, phone int) *Node {
    // Your code here
}

func main() {
    // Step 1 setup done
}

Hint

Use recursion to insert the phone number. If node is nil, create a new Node. Otherwise, compare phone with node.phone and insert left or right accordingly.

3

Insert Phone Numbers

In the main function, insert these phone numbers into the BST using the insert function and assign the result back to root: 5551234, 5555678, 5550000, 5559999.

DSA Go

package main

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

var root *Node = nil

func insert(node *Node, phone int) *Node {
    if node == nil {
        return &Node{phone: phone}
    }
    if phone < node.phone {
        node.left = insert(node.left, phone)
    } else {
        node.right = insert(node.right, phone)
    }
    return node
}

func main() {
    root = insert(root, 5551234)
    root = insert(root, 5555678)
    root = insert(root, 5550000)
    root = insert(root, 5559999)
    // Your code here
}

Hint

Call insert four times with the given phone numbers and assign the result to root each time.

4

Print BST In-Order

Create a function called inOrder that takes a *Node and prints the phone numbers in ascending order separated by spaces. Then call inOrder(root) in main to print the sorted phone numbers.

DSA Go

package main

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

var root *Node = nil

func insert(node *Node, phone int) *Node {
    if node == nil {
        return &Node{phone: phone}
    }
    if phone < node.phone {
        node.left = insert(node.left, phone)
    } else {
        node.right = insert(node.right, phone)
    }
    return node
}

func inOrder(node *Node) {
    // Your code here
}

func main() {
    root = insert(root, 5551234)
    root = insert(root, 5555678)
    root = insert(root, 5550000)
    root = insert(root, 5559999)
    inOrder(root)
}

Hint

Use recursion to print left subtree, then current node's phone, then right subtree. Use fmt.Printf("%d ", node.phone) to print each phone number with a space.