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.