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.