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.