BST Search Operation in DSA Go

Mental Model

A binary search tree lets you quickly find a value by comparing and moving left or right at each step.

Analogy: Like looking for a name in a phone book by opening to the middle and deciding to go left or right depending on the name.

      5
     / \
    3   7
   / \   \
  2   4   8
 ↑

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, search for value 4

Goal: Find if value 4 exists in the BST and show the path taken

Step 1: Start at root node with value 5

5 [curr↑] -> 3 -> 7 -> 2 -> 4 -> 8

Why: We always start searching from the root of the BST

Step 2: Compare 4 with 5, 4 < 5, move to left child 3

5 -> 3 [curr↑] -> 7 -> 2 -> 4 -> 8

Why: Since 4 is less than 5, search continues in left subtree

Step 3: Compare 4 with 3, 4 > 3, move to right child 4

5 -> 3 -> 4 [curr↑] -> 7 -> 2 -> 8

Why: 4 is greater than 3, so we go right in the BST

Step 4: Found node with value 4, search ends

5 -> 3 -> 4 [curr↑] -> 7 -> 2 -> 8

Why: We found the value we were looking for

Result:

5 -> 3 -> 4 -> null (value 4 found)

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
    val   int
    left  *Node
    right *Node
}

func (n *Node) Search(value int) *Node {
    if n == nil {
        return nil // reached leaf, not found
    }
    if value == n.val {
        return n // found the value
    } else if value < n.val {
        return n.left.Search(value) // search left subtree
    } else {
        return n.right.Search(value) // search right subtree
    }
}

func main() {
    root := &Node{val: 5}
    root.left = &Node{val: 3}
    root.right = &Node{val: 7}
    root.left.left = &Node{val: 2}
    root.left.right = &Node{val: 4}
    root.right.right = &Node{val: 8}

    searchVal := 4
    found := root.Search(searchVal)
    if found != nil {
        fmt.Printf("%d -> %d -> %d -> null (value %d found)\n", root.val, root.left.val, found.val, searchVal)
    } else {
        fmt.Printf("Value %d not found in BST\n", searchVal)
    }
}

if n == nil {

check if reached end of branch without finding value

if value == n.val {

found the node with the target value

else if value < n.val {

go left if target is smaller than current node

else {

go right if target is greater than current node

Output

5 -> 3 -> 4 -> null (value 4 found)

Complexity Analysis

Time: O(h) where h is the height of the tree, because we move down one level each step

Space: O(h) due to recursive call stack in worst case of skewed tree

vs Alternative: Compared to linear search in an unsorted list O(n), BST search is faster if tree is balanced

Edge Cases

search value not in BST

search returns nil after reaching leaf node

DSA Go

if n == nil { return nil }

search in empty BST (root is nil)

search returns nil immediately

DSA Go

if n == nil { return nil }

search value is at root node

search returns root node immediately

DSA Go

if value == n.val { return n }

When to Use This Pattern

When you need to find if a value exists quickly in a sorted tree structure, use BST search because it narrows down the search path by comparing values.

Common Mistakes

Mistake: Not checking for nil before accessing node fields causing runtime errors
Fix: Always check if current node is nil before proceeding

Mistake: Searching both left and right subtrees instead of choosing one side
Fix: Use value comparison to decide only one subtree to search

Summary

Searches for a value in a binary search tree by comparing and moving left or right.

Use when you want fast lookup in a sorted tree structure.

The key insight is to use the tree's order property to skip half the nodes at each step.

Practice

1. What does the search operation in a Binary Search Tree (BST) do?

easy

A. Finds whether a given value exists in the BST

B. Deletes a node from the BST

C. Inserts a new node into the BST

D. Traverses all nodes in the BST

Solution

1. Step 1: Understand the purpose of BST search

   The search operation is designed to check if a specific value is present in the BST.

2. Step 2: Differentiate from other operations

   Insertion adds nodes, deletion removes nodes, and traversal visits nodes. Search only checks for existence.

3. Final Answer:

   Finds whether a given value exists in the BST -> Option A

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search returns the node always
• Assuming search traverses all nodes

2. Which of the following is the correct Go function signature for a BST search method that returns a boolean indicating if a value exists?

easy

A. func Search(val int) *Node

B. func (root *Node) Search(val int) bool

C. func (root Node) Search(val string) bool

D. func Search(root Node, val int) int

Solution

1. Step 1: Identify method receiver and return type

   BST search is usually a method on a pointer to Node and returns bool for found or not.

2. Step 2: Check parameter types and return type

   func (root *Node) Search(val int) bool uses pointer receiver, int parameter, and bool return which matches the expected signature.

3. Final Answer:

   func (root *Node) Search(val int) bool -> Option B

4. Quick Check:

   Pointer receiver + bool return = func (root *Node) Search(val int) bool [OK]

Hint: Search returns bool, uses pointer receiver for tree nodes [OK]

Common Mistakes:

• Using value receiver instead of pointer
• Wrong parameter or return types
• Confusing method vs function signatures

3. Given the BST below and the Go code snippet, what will be the output? BST structure: ``` 10 / \ 5 15 / 3 ``` Go code:

found := root.Search(3)
fmt.Println(found)

medium

A. true

B. false

C. nil

D. runtime error

Solution

1. Step 1: Trace the search for value 3 in the BST

   Starting at root 10, 3 < 10, go left to 5; 3 < 5, go left to 3; found node with value 3.

2. Step 2: Understand the returned value and print output

   Search returns true because 3 exists; printing true outputs 'true'.

3. Final Answer:

   true -> Option A

4. Quick Check:

   3 found in BST = true [OK]

Hint: Follow BST left/right rules to find value [OK]

Common Mistakes:

• Assuming search returns node instead of bool
• Confusing true/false output
• Ignoring BST structure when tracing

4. The following Go code for BST search has a bug. What is the bug?

func (root *Node) Search(val int) bool {
    if root == nil {
        return false
    }
    if root.Value == val {
        return true
    }
    if val < root.Value {
        return root.Search(val)
    } else {
        return root.Search(val)
    }
}

medium

A. Base case for nil root is missing

B. Uses value receiver instead of pointer

C. Returns int instead of bool

D. Recursive calls do not move to left or right child nodes

Solution

1. Step 1: Analyze recursive calls in search method

   Both recursive calls use root.Search(val) without moving to root.Left or root.Right, causing infinite recursion.

2. Step 2: Identify correct recursive calls

   Should call root.Left.Search(val) if val < root.Value, else root.Right.Search(val) to move down the tree.

3. Final Answer:

   Recursive calls do not move to left or right child nodes -> Option D

4. Quick Check:

   Recursive calls must move down tree [OK]

Hint: Recursive calls must go to left or right child [OK]

Common Mistakes:

• Calling search on same node causing infinite loop
• Missing base case for nil
• Wrong return types

5. You want to search for a value in a BST but also count how many nodes you visited during the search. Which modification to the search function is best?

hard

A. Use a global variable to count nodes visited during search

B. Return the node instead of bool and count nodes outside the function

C. Add a counter parameter passed by pointer and increment it on each node visited

D. Modify the BST to store counts in each node

Solution

1. Step 1: Understand the need to count nodes during search

   Counting nodes visited requires tracking each node checked during recursion.

2. Step 2: Choose method to count nodes visited

   Passing a pointer to a counter variable and incrementing it at each node visit allows accurate counting without side effects.

3. Final Answer:

   Add a counter parameter passed by pointer and increment it on each node visited -> Option C

4. Quick Check:

   Pass counter pointer to track visits [OK]

Hint: Pass counter pointer to track nodes visited [OK]

Common Mistakes:

• Using global variables causing side effects
• Counting outside search missing recursive visits
• Changing BST structure unnecessarily