BST Insert Operation in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes in BST

What is the printed state of the BST after inserting the values 10, 5, 15, 3, 7 in that order? The BST is printed in-order (left -> root -> right).

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)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}

func inorder(root *Node) {
    if root == nil {
        return
    }
    inorder(root.left)
    fmt.Print(root.val, " -> ")
    inorder(root.right)
}

func main() {
    var root *Node
    values := []int{10, 5, 15, 3, 7}
    for _, v := range values {
        root = insert(root, v)
    }
    inorder(root)
    fmt.Print("null\n")
}

A 3 -> 5 -> 7 -> 10 -> 15 -> null

B 10 -> 5 -> 15 -> 3 -> 7 -> null

C 15 -> 10 -> 7 -> 5 -> 3 -> null

D 3 -> 7 -> 5 -> 10 -> 15 -> null

💡 Hint

Remember that in-order traversal of a BST prints values in ascending order.

In-order traversal visits nodes in ascending order for BSTs. After inserting 10, 5, 15, 3, 7, the sorted order is 3, 5, 7, 10, 15.

❓ Predict Output

intermediate

Output after inserting duplicate value in BST

What is the printed state of the BST after inserting the values 8, 3, 10, 3 in that order? Assume duplicates are inserted to the right subtree.

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)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}

func inorder(root *Node) {
    if root == nil {
        return
    }
    inorder(root.left)
    fmt.Print(root.val, " -> ")
    inorder(root.right)
}

func main() {
    var root *Node
    values := []int{8, 3, 10, 3}
    for _, v := range values {
        root = insert(root, v)
    }
    inorder(root)
    fmt.Print("null\n")
}

A 8 -> 3 -> 3 -> 10 -> null

B 3 -> 8 -> 3 -> 10 -> null

C 3 -> 3 -> 8 -> 10 -> null

D 3 -> 8 -> 10 -> 3 -> null

💡 Hint

Duplicates go to the right subtree, so the second 3 is inserted as right child of the first 3.

Inserting duplicate 3 goes to the right subtree of the first 3. In-order traversal prints nodes in ascending order including duplicates.

🔧 Debug

advanced

Identify the bug in BST insert function

The following Go code attempts to insert a value into a BST but causes infinite recursion. What is the bug?

DSA Go

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

A The recursive calls do not assign the returned node back to root.left or root.right.

B The base case is missing for root == nil.

C The comparison should be val < root.val, not val <= root.val.

D The function should return void, not *Node.

💡 Hint

Check if the tree links are updated after recursion.

The recursive calls must assign the returned node to root.left or root.right to update the tree structure. Without assignment, the tree remains unchanged causing infinite recursion.

🧠 Conceptual

advanced

Number of nodes after insertions in BST

If you insert the values 20, 10, 30, 25, 35, 10 into an empty BST (duplicates allowed), how many nodes will the BST contain?

A 7

B 5

C 4

D 6

💡 Hint

Duplicates are inserted as new nodes in the right subtree.

All values including the duplicate 10 are inserted as separate nodes. So total nodes = 6.

🚀 Application

expert

BST structure after complex insertions

After inserting the values 50, 30, 70, 20, 40, 60, 80, 65 into an empty BST, what is the in-order traversal output?

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)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}

func inorder(root *Node) {
    if root == nil {
        return
    }
    inorder(root.left)
    fmt.Print(root.val, " -> ")
    inorder(root.right)
}

func main() {
    var root *Node
    values := []int{50, 30, 70, 20, 40, 60, 80, 65}
    for _, v := range values {
        root = insert(root, v)
    }
    inorder(root)
    fmt.Print("null\n")
}

A 20 -> 30 -> 40 -> 50 -> 65 -> 60 -> 70 -> 80 -> null

B 20 -> 30 -> 40 -> 50 -> 60 -> 65 -> 70 -> 80 -> null

C 50 -> 30 -> 20 -> 40 -> 70 -> 60 -> 65 -> 80 -> null

D 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 65 -> 80 -> null

💡 Hint

In-order traversal prints nodes in ascending order.

In-order traversal of BST prints values sorted. The inserted values sorted are 20, 30, 40, 50, 60, 65, 70, 80.

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