BST Insert Operation in DSA Go

Mental Model

A binary search tree keeps values in order by placing smaller values to the left and larger to the right. Inserting means finding the right empty spot following this rule.

Analogy: Imagine a sorted family tree where each person has a left child who is younger and a right child who is older. To add a new person, you walk down the tree comparing ages until you find an empty spot.

    5
   / \
  3   7
 / \   \
2   4   8
↑ root

Dry Run Walkthrough

Input: Insert value 6 into BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8

Goal: Add 6 to the BST in the correct position to keep the order

Step 1: Start at root node 5

5 [curr->5] -> 3 -> 7 -> 2 -> 4 -> 8

Why: We begin comparing from the root to find where to insert

Step 2: 6 is greater than 5, move to right child 7

5 -> 3 -> 7 [curr->7] -> 2 -> 4 -> 8

Why: Since 6 > 5, we go right to find the correct spot

Step 3: 6 is less than 7, move to left child which is null

5 -> 3 -> 7 [curr->null] -> 2 -> 4 -> 8

Why: 6 < 7 means we go left, but left child is empty, so insert here

Step 4: Insert 6 as left child of 7

    5
   / \
  3   7
 / \  / 
2  4 6  8

Why: Placing 6 here keeps the BST property intact

Result:

    5
   / \
  3   7
 / \  / 
2  4 6  8

Annotated Code

DSA Go

package main

import "fmt"

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

func insert(root *Node, val int) *Node {
	if root == nil {
		return &Node{val: val}
	}
	if val < root.val {
		root.left = insert(root.left, val) // go left to insert smaller value
	} else {
		root.right = insert(root.right, val) // go right to insert larger or equal value
	}
	return root
}

func printBST(root *Node) {
	if root == nil {
		return
	}
	printBST(root.left)
	fmt.Printf("%d ", root.val)
	printBST(root.right)
}

func main() {
	root := &Node{val: 5}
	root.left = &Node{val: 3}
	root.right = &Node{val: 7}
	root.left.left = &Node{val: 2}
	root.left.right = &Node{val: 4}
	root.right.right = &Node{val: 8}

	root = insert(root, 6)
	printBST(root)
	fmt.Println()
}

if root == nil { return &Node{val: val} }

insert new node when we find empty spot

if val < root.val { root.left = insert(root.left, val)

go left if value is smaller

else { root.right = insert(root.right, val)

go right if value is larger or equal

return root

return updated subtree root after insertion

Output

2 3 4 5 6 7 8 

Complexity Analysis

Time: O(h) where h is tree height because we follow one path down to insert

Space: O(h) due to recursion stack for the path from root to insertion point

vs Alternative: Compared to inserting in an unsorted tree which is O(1), BST insert is slower but keeps data ordered for fast search

Edge Cases

Empty tree (root is nil)

Insert creates a new root node

DSA Go

if root == nil {
	return &Node{val: val}
}

Insert value smaller than all existing nodes

Inserted as leftmost leaf

DSA Go

if val < root.val {
	root.left = insert(root.left, val)

Insert duplicate value

Inserted in right subtree to keep BST property

DSA Go

else {
	root.right = insert(root.right, val)

When to Use This Pattern

When you need to keep data sorted and quickly find or add values, use BST insert to place new values in order by comparing and moving left or right.

Common Mistakes

Mistake: Not updating the parent's left or right pointer after recursive insert
Fix: Assign the result of recursive insert back to root.left or root.right

Mistake: Inserting duplicates on the left side breaking BST property
Fix: Always insert duplicates on the right subtree

Summary

Inserts a new value into the binary search tree while keeping it ordered.

Use when you want to add values to a BST so that search remains efficient.

The key is to compare and move left or right until you find an empty spot to insert.

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