BST Property and Why It Matters in DSA Go

Mental Model

A Binary Search Tree keeps smaller values on the left and bigger values on the right, making searching fast.

Analogy: Imagine a library where books are arranged so that all books with titles starting with letters before 'M' are on the left shelves, and those after 'M' are on the right shelves. This helps you find a book quickly without checking every shelf.

       10
      /  \
     5    15
    / \     \
   3   7     20

Dry Run Walkthrough

Input: BST with nodes 10, 5, 15, 3, 7, 20; search for value 7

Goal: Show how BST property helps find 7 quickly by deciding left or right at each step

Step 1: Start at root node 10

       [10↑]
      /    \
     5      15
    / \       \
   3   7       20

Why: We begin search at the root to compare the target value

Step 2: Compare 7 with 10; 7 is less, go left to node 5

       10
      /    \
    [5↑]    15
    / \       \
   3   7       20

Why: BST property says smaller values are on the left, so we go left

Step 3: Compare 7 with 5; 7 is greater, go right to node 7

       10
      /    \
     5      15
    /   \     \
   3   [7↑]    20

Why: BST property says bigger values are on the right, so we go right

Step 4: Found node 7, stop search

       10
      /    \
     5      15
    /   \     \
   3   [7↑]    20

Why: We found the target value, so search ends

Result:

       10
      /    \
     5      15
    /   \     \
   3   [7↑]    20
Answer: Found 7

Annotated Code

DSA Go

package main

import "fmt"

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

func searchBST(root *Node, target int) *Node {
    curr := root
    for curr != nil {
        if target == curr.val {
            return curr // found target
        } else if target < curr.val {
            curr = curr.left // go left for smaller values
        } else {
            curr = curr.right // go right for bigger values
        }
    }
    return nil // target not found
}

func main() {
    root := &Node{val: 10}
    root.left = &Node{val: 5}
    root.right = &Node{val: 15}
    root.left.left = &Node{val: 3}
    root.left.right = &Node{val: 7}
    root.right.right = &Node{val: 20}

    target := 7
    found := searchBST(root, target)
    if found != nil {
        fmt.Printf("Found %d\n", found.val)
    } else {
        fmt.Printf("Value %d not found\n", target)
    }
}

curr := root

start search at root node

for curr != nil {

continue until we find target or reach end

if target == curr.val {

check if current node is target

return curr // found target

stop search and return node

else if target < curr.val {

go left if target smaller than current

curr = curr.left // go left for smaller values

move to left child

else {

go right if target bigger than current

curr = curr.right // go right for bigger values

move to right child

Output

Found 7

Complexity Analysis

Time: O(h) where h is tree height because we follow one path down the tree

Space: O(1) because we use only a few pointers, no extra storage

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

Edge Cases

Empty tree (root is nil)

Search returns nil immediately, meaning value not found

DSA Go

for curr != nil {

Target value not in tree

Search reaches a nil child and returns nil

DSA Go

for curr != nil {

Target is root node value

Search finds target immediately at root and returns it

DSA Go

if target == curr.val {

When to Use This Pattern

When you need to search or insert values quickly in a sorted way, look for the BST property to guide your path and avoid checking every node.

Common Mistakes

Mistake: Not comparing target with current node value to decide left or right
Fix: Always compare target with current node value to choose correct subtree

Mistake: Going left when target is greater or right when target is smaller
Fix: Follow BST rule: smaller values go left, bigger go right

Summary

It keeps smaller values left and bigger values right to speed up search.

Use it when you want fast search, insert, or delete in sorted data.

The key is comparing target with current node to decide direction.