BST vs Hash Map Trade-offs for Ordered Data in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on BST Insertions

Given the following sequence of insertions into an empty Binary Search Tree (BST), what is the output of an inorder traversal?

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, res *[]int) {
    if root == nil {
        return
    }
    inorder(root.left, res)
    *res = append(*res, root.val)
    inorder(root.right, res)
}

func main() {
    var root *Node
    values := []int{50, 30, 70, 20, 40, 60, 80}
    for _, v := range values {
        root = insert(root, v)
    }
    var result []int
    inorder(root, &result)
    fmt.Println(result)
}

A [20, 40, 30, 60, 80, 70, 50]

B [20, 30, 40, 50, 60, 70, 80]

C [80, 70, 60, 50, 40, 30, 20]

D [50, 30, 20, 40, 70, 60, 80]

💡 Hint

Inorder traversal of a BST always returns values in sorted order.

Inorder traversal visits nodes in ascending order for BSTs. The inserted values will be sorted as [20, 30, 40, 50, 60, 70, 80].

🧠 Conceptual

intermediate

Why Use BST Over Hash Map for Ordered Data?

Which of the following is the main reason to choose a Binary Search Tree (BST) over a Hash Map when you need ordered data?

A BST maintains elements in sorted order allowing range queries and ordered traversal.

B BST provides faster average lookup time than Hash Map.

C BST uses less memory than Hash Map in all cases.

D BST automatically handles duplicate keys better than Hash Map.

💡 Hint

Think about what data structure allows you to get sorted data easily.

BST keeps data sorted by design, enabling ordered traversal and range queries, which Hash Maps do not support natively.

❓ Predict Output

advanced

Hash Map Key Existence Check Output

What is the output of the following Go code snippet that uses a map to check key existence?

DSA Go

package main

import "fmt"

func main() {
    m := map[int]string{1: "one", 2: "two", 3: "three"}
    val, ok := m[4]
    fmt.Println(val, ok)
}

A panic: runtime error: invalid memory address or nil pointer dereference

B "four" true

C "zero" false

D "" false

💡 Hint

Accessing a non-existent key in a Go map returns zero value and false for existence.

When a key is not found in a Go map, the zero value of the value type is returned along with false.

🚀 Application

advanced

Choosing Data Structure for Range Queries

You need to store a large set of integer keys and frequently perform queries to find all keys within a given range. Which data structure is best suited for this task?

A Binary Search Tree (BST) because it supports efficient range queries via inorder traversal.

B Hash Map because it provides constant time lookup for any key.

C Array because it allows direct indexing of keys.

D Stack because it supports last-in-first-out access.

💡 Hint

Think about which structure keeps keys sorted and allows scanning between two values.

BSTs keep keys sorted and allow efficient traversal of keys in a range, unlike Hash Maps or stacks.

🔧 Debug

expert

Why Does This BST Insertion Cause Infinite Recursion?

Consider this Go code for inserting into a BST. Why does it cause infinite recursion?

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 Because the function does not handle duplicate values correctly.

B Because the base case is missing for nil root.

C Because the recursive calls do not assign the returned node back to root.left or root.right.

D Because the function returns root before recursion completes.

💡 Hint

Check if the recursive calls update the tree links properly.

The recursive calls must assign the returned node to root.left or root.right to update the tree; otherwise, the tree structure is never updated, causing infinite recursion.