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.

Practice

1. What is the main purpose of the Insert operation in a Binary Search Tree (BST)?

easy

A. To balance the BST after insertion

B. To add a new node while keeping the BST property intact

C. To find the maximum value in the BST

D. To delete a node from the BST

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Purpose of Insert

   Insert adds a new node in the correct position to keep this order intact.

3. Final Answer:

   To add a new node while keeping the BST property intact -> Option B

4. Quick Check:

   Insert = Add node correctly [OK]

Hint: Insert adds nodes preserving BST order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert finds max value

2. Which of the following is the correct way to declare a BST node struct in Go for insertion?

easy

A. type Node struct { value int; left *Node; right *Node }

B. type Node struct { val int; left Node; right Node }

C. type Node struct { value int; left Node; right Node }

D. type Node struct { value int; left *Node; right Node }

Solution

1. Step 1: Understand pointer usage in Go structs

   BST nodes must use pointers for left and right to link nodes dynamically.

2. Step 2: Check each option

   type Node struct { value int; left *Node; right *Node } uses pointers (*Node) for left and right, correct for BST links.

3. Final Answer:

   type Node struct { value int; left *Node; right *Node } -> Option A

4. Quick Check:

   Use pointers for child nodes [OK]

Hint: Use *Node pointers for left and right children [OK]

Common Mistakes:

• Using value types instead of pointers for children
• Mixing pointer and non-pointer types incorrectly
• Incorrect field names like 'val' instead of 'value'

3. Given the following BST and insertion code snippet in Go, what will be the inorder traversal output after inserting 6?

root := &Node{value: 5}
root.left = &Node{value: 3}
root.right = &Node{value: 7}
Insert(root, 6)
// Inorder traversal function prints nodes in ascending order

medium

A. 3 5 6 7

B. 3 5 7 6

C. 5 3 6 7

D. 3 6 5 7

Solution

1. Step 1: Understand BST structure before insertion

   Initial tree: 5 root, 3 left child, 7 right child.

2. Step 2: Insert 6

   6 is less than 7 but greater than 5, so it becomes left child of 7.

3. Step 3: Inorder traversal

   Inorder visits left, root, right: 3, 5, 6, 7.

4. Final Answer:

   3 5 6 7 -> Option A

5. Quick Check:

   Inorder after insert = 3 5 6 7 [OK]

Hint: Insert left if smaller, right if larger; inorder sorts [OK]

Common Mistakes:

• Placing 6 as right child of 5 directly
• Confusing inorder traversal order
• Ignoring BST property during insertion

4. Identify the error in this Go function for inserting a value into a BST:

func Insert(root *Node, val int) *Node {
  if root == nil {
    return &Node{value: val}
  }
  if val < root.value {
    root.left = Insert(root.left, val)
  } else if val > root.value {
    root.right = Insert(root.right, val)
  }
  return root
}

medium

A. The function uses wrong comparison operators (< and >)

B. The function returns nil instead of root

C. The function does not handle duplicate values explicitly

D. The function does not create new nodes correctly

Solution

1. Step 1: Review function logic

   Function inserts recursively left or right based on value comparison.

2. Step 2: Check duplicate handling

   When val equals root.value, no insertion or special handling occurs.

3. Step 3: Identify error

   Duplicates are ignored silently; function should handle or document this case.

4. Final Answer:

   The function does not handle duplicate values explicitly -> Option C

5. Quick Check:

   Duplicates need explicit handling [OK]

Hint: Check if duplicates are handled in insert [OK]

Common Mistakes:

• Assuming duplicates insert automatically
• Returning nil instead of root
• Using wrong comparison signs

5. You have a BST with nodes 10, 5, 15, 3, 7, 12, 18. You want to insert 6. Which sequence of nodes will you visit during the insertion process?

hard

A. 10 -> 5 -> 7 -> 6

B. 10 -> 15 -> 12

C. 10 -> 5 -> 3

D. 10 -> 5 -> 7

Solution

1. Step 1: Start at root 10

   6 is less than 10, move to left child 5.

2. Step 2: Compare with 5

   6 is greater than 5, move to right child 7.

3. Step 3: Compare with 7

   6 is less than 7, insert as left child of 7.

4. Final Answer:

   10 -> 5 -> 7 -> Option D

5. Quick Check:

   Traverse nodes comparing values [OK]

Hint: Follow BST rules: left if smaller, right if larger [OK]

Common Mistakes:

• Visiting wrong child nodes
• Including inserted node in visited sequence
• Confusing greater and smaller comparisons