BST Insert Operation in DSA Go - Execution Trace

Concept Flow - BST Insert Operation

Start at root

↓

Compare new value with current node

↓

Go left

↓

Is child null?

↓

Insert new node

Start at the root, compare the new value with current node, go left if smaller, right if larger or equal, repeat until a null child is found, then insert the new node there.

Execution Sample

DSA Go

func Insert(root *Node, val int) *Node {
  if root == nil {
    return &Node{Val: val, Left: nil, Right: nil}
  }
  if val < root.Val {
    root.Left = Insert(root.Left, val)
  } else {
    root.Right = Insert(root.Right, val)
  }
  return root
}

This code inserts a value into a BST by recursively finding the correct spot and adding a new node.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Start at root	10	10 vs 15	None	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:5 │ │ data:20│ │ left:──┼──→ ∅ │ │ left:∅ │ │ right:─┼──→ ────────┼──→ ∅ │ └────────┘ └────────┘ └────────┘ root
2	Compare 15 > 10, go right	10	15 > 10	Move current to right child (20)	Same as above, current pointer moves to node 20
3	Compare 15 < 20, go left	20	15 < 20	Move current to left child (null)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:5 │ │ data:20│ │ left:──┼──→ ∅ │ │ left:∅ │ │ right:─┼──→ ────────┼──→ ∅ │ └────────┘ └────────┘ └────────┘ root
4	Left child is null, insert new node 15	null	Insert here	Set left child of 20 to new node 15	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:5 │ │ data:20│ │ data:15│ │ left:──┼──→ ∅ │ │ left:──┼──→ ∅ │ │ left:∅ │ │ right:─┼──→ ────────┼──→ ────────┼──→ ∅ │ │ right:∅│ └────────┘ └────────┘ └────────┘ └────────┘ root
5	Return to root, insertion complete	10	Done	No changes	Same as step 4

💡 Insertion done when a null child is found and new node is linked there.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
current	10 (root)	20 (right child of 10)	null (left child of 20)	15 (new node inserted)	15 (new node)
root.Left	5	5	5	5	5
root.Right	20	20	20	20	20 with left child 15

Key Moments - 3 Insights

Why do we move to the right child when the new value is greater or equal?

In the execution_table step 2, since 15 > 10, we move right to keep BST property: left < node < right.

What happens when we find a null child during traversal?

As shown in step 4, when current is null, we insert the new node there by linking it to the parent's pointer.

Why do we return the root at the end?

Returning root (step 5) ensures the BST structure is maintained and the original root pointer is preserved.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the current node's value?

A 20

B 15

C 10

D null

💡 Hint

Check the 'Current Node' column at step 3 in the execution_table.

At which step does the new node get inserted?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for the step where 'Pointer Changes' mention setting a child to the new node.

If we insert a value smaller than 5, which pointer would change?

A root.Left

B root.Right

C left child of 5

D right child of 20

💡 Hint

Refer to the variable_tracker and concept_flow to see where smaller values go.

Concept Snapshot

BST Insert Operation:
- Start at root node
- Compare new value with current node
- Go left if smaller, right if larger or equal
- Repeat until null child found
- Insert new node at null position
- Return root to keep tree intact

Full Transcript

The BST Insert Operation starts at the root node. We compare the new value with the current node's value. If the new value is smaller, we move to the left child; if larger or equal, we move to the right child. We repeat this process until we find a null child pointer. At that point, we insert the new node by linking it to the parent's pointer. Finally, we return the root node to maintain the tree structure. This process ensures the binary search tree property is preserved.

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