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.