BST Search Operation in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Search for Existing Value

What is the output of the following Go code that searches for the value 15 in a BST?

DSA Go

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func searchBST(root *Node, target int) *Node {
    if root == nil || root.val == target {
        return root
    }
    if target < root.val {
        return searchBST(root.left, target)
    }
    return searchBST(root.right, target)
}
func main() {
    root := &Node{val: 10}
    root.left = &Node{val: 5}
    root.right = &Node{val: 20}
    root.right.left = &Node{val: 15}
    result := searchBST(root, 15)
    if result != nil {
        fmt.Println(result.val)
    } else {
        fmt.Println("Not found")
    }
}

A 15

B 20

C 5

D Not found

💡 Hint

Trace the search path comparing target with node values.

The search starts at root (10). Since 15 > 10, it moves to right subtree (20). Since 15 < 20, it moves to left subtree of 20 (15). The code correctly finds 15.

❓ Predict Output

intermediate

Output of BST Search for Non-Existing Value

What is the output of the following Go code that searches for the value 17 in a BST?

DSA Go

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func searchBST(root *Node, target int) *Node {
    if root == nil || root.val == target {
        return root
    }
    if target < root.val {
        return searchBST(root.left, target)
    }
    return searchBST(root.right, target)
}
func main() {
    root := &Node{val: 10}
    root.left = &Node{val: 5}
    root.right = &Node{val: 20}
    root.right.left = &Node{val: 15}
    result := searchBST(root, 17)
    if result != nil {
        fmt.Println(result.val)
    } else {
        fmt.Println("Not found")
    }
}

A 15

B 5

C 20

D Not found

💡 Hint

Check if the value 17 exists in the tree by following the search path.

The search starts at root (10). Since 17 > 10, it moves to right subtree (20). Since 17 < 20, it moves to left subtree of 20 (15). Since 17 > 15, it moves to right subtree of 15, which is nil. So, the value 17 is not found in the BST.

🧠 Conceptual

advanced

Understanding BST Search Path

In a BST, which path does the search algorithm follow to find a target value?

A Go left if target is less than current node, else go right

B Go right if target is less than current node, else go left

C Always go left child regardless of target value

D Search both left and right subtrees simultaneously

💡 Hint

Think about how BST property orders values.

BST property: left child values are less, right child values are greater. So search goes left if target is smaller, right if larger.

🔧 Debug

advanced

Identify the Bug in BST Search Code

What error will the following Go code produce when searching for a value in a BST?

DSA Go

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func searchBST(root *Node, target int) *Node {
    if root == nil {
        return nil
    }
    if root.val == target {
        return root
    }
    if target > root.val {
        return searchBST(root.left, target)
    }
    return searchBST(root.right, target)
}
func main() {
    root := &Node{val: 10}
    root.left = &Node{val: 5}
    root.right = &Node{val: 20}
    result := searchBST(root, 5)
    if result != nil {
        fmt.Println(result.val)
    } else {
        fmt.Println("Not found")
    }
}

A Prints 20

B Prints 5

C Prints "Not found"

D Compilation error

💡 Hint

Check the direction of recursive calls for target > root.val.

The code incorrectly calls searchBST on root.left when target > root.val, which should be root.right. When searching for 5 (< 10), since the condition target > root.val is false, it takes the else branch and searches root.right instead of root.left, missing the node 5 and printing "Not found".

🚀 Application

expert

Number of Nodes Visited in BST Search

Given a BST with nodes inserted in this order: 10, 5, 15, 3, 7, 12, 18. How many nodes will be visited when searching for the value 7?

A 4

B 3

C 2

D 5

💡 Hint

Trace the search path from root to the target node counting nodes visited.

Search path: 10 (root) -> 5 (left child) -> 7 (right child of 5). Total nodes visited = 3.