BST Property and Why It Matters in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 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 property is maintained during insertion.

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
    vals := []int{10, 5, 15, 3, 7}
    for _, v := range vals {
        root = insert(root, v)
    }
    inorder(root)
    fmt.Print("null\n")
}

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

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

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

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

💡 Hint

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

Inorder traversal of a BST visits nodes in ascending order because left subtree nodes are smaller, root is next, then right subtree nodes are larger.

Inserted values 10, 5, 15, 3, 7 create a BST where inorder traversal prints: 3 -> 5 -> 7 -> 10 -> 15 -> null.

🧠 Conceptual

intermediate

Why BST Property Matters for Search Efficiency

Why does maintaining the BST property help in searching for a value efficiently?

A Because it sorts values after every insertion to speed up search.

B Because it stores all values in a linked list for quick access.

C Because it allows skipping half of the tree at each step, similar to binary search.

D Because it uses hashing to find values instantly.

💡 Hint

Think about how binary search works on sorted arrays.

The BST property ensures left children are smaller and right children are larger than the node, allowing the search to decide which subtree to explore next.

This halves the search space at each step, making search efficient like binary search.

🔧 Debug

advanced

Identify the Error in BST Insertion Code

What error will this Go code produce when inserting values into a BST?

DSA Go

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
}

// Node struct is defined as usual.

A Runtime panic due to nil pointer dereference.

B Stack overflow due to infinite recursion on duplicates.

C Compilation error due to missing return statement.

D No error; duplicates go to left subtree.

💡 Hint

Check how duplicates are handled in the code.

The code allows duplicates by inserting them into the left subtree (val <= root.val).

This is valid and will not cause errors or infinite recursion.

❓ Predict Output

advanced

Output After Deleting a Node in BST

Given a BST with nodes 20, 10, 30, 5, 15, what is the inorder traversal output after deleting node 10?

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 minValueNode(node *Node) *Node {
    current := node
    for current.left != nil {
        current = current.left
    }
    return current
}

func deleteNode(root *Node, val int) *Node {
    if root == nil {
        return root
    }
    if val < root.val {
        root.left = deleteNode(root.left, val)
    } else if val > root.val {
        root.right = deleteNode(root.right, val)
    } else {
        if root.left == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.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
    vals := []int{20, 10, 30, 5, 15}
    for _, v := range vals {
        root = insert(root, v)
    }
    root = deleteNode(root, 10)
    inorder(root)
    fmt.Print("null\n")
}

A 5 -> 15 -> 20 -> 30 -> null

B 5 -> 10 -> 15 -> 20 -> 30 -> null

C 15 -> 5 -> 20 -> 30 -> null

D 5 -> 20 -> 30 -> null

💡 Hint

When deleting a node with two children, replace it with the smallest node in the right subtree.

Node 10 has two children (5 and 15). Deleting it replaces 10 with 15 (smallest in right subtree).

Inorder traversal after deletion: 5 -> 15 -> 20 -> 30 -> null.

🧠 Conceptual

expert

Effect of Violating BST Property on Search

If a binary tree does not maintain the BST property, what is the impact on search operation efficiency?

A Search becomes constant time because nodes are unordered.

B Search becomes linear time, similar to searching an unsorted list.

C Search remains logarithmic time due to tree structure.

D Search cannot be performed at all.

💡 Hint

Think about how the BST property helps reduce search space.

Without BST property, you cannot decide which subtree to explore, so you may need to check every node.

This makes search time linear, like scanning a list.