BST Search - Go DSA

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Go DSA implementation can be compared directly with the rest of the DSA track.

search path A comparison chooses one subtree at each step, so whole branches are skipped.

Visual walkthrough

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Basic Implementation

                            basic.go
                        

                            package main

import (
    "fmt"
    "strings"
)

type Node struct { value int; left *Node; right *Node }
func render(node *Node) string {
    if node == nil { return "_" }
    if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }
    return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))
}
func sampleTree() *Node {
    return &Node{4, &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}, &Node{6, &Node{5, nil, nil}, &Node{7, nil, nil}}}
}
func listString(values []int) string {
    parts := []string{}
    for _, value := range values { parts = append(parts, fmt.Sprintf("%d", value)) }
    return "[" + strings.Join(parts, ", ") + "]"
}
func search(root *Node, target int) bool { node := root; for node != nil { if target == node.value { return true }; if target < node.value { node = node.left } else { node = node.right } }; return false }
func main() { root := sampleTree(); if search(root, 5) { fmt.Println("5 found") } else { fmt.Println("5 not found") }; if search(root, 8) { fmt.Println("8 found") } else { fmt.Println("8 not found") } }

                        

Complexity

Time: O(h) per search
Space: O(1) iterative

Implementation notes

Go uses type Node struct { value int; left *Node; right *Node }; the sample tree is built from *Node pointers with nil child links.
search(root *Node, target int) bool is iterative. It copies root into a local node cursor, reads pointers, and never mutates the tree.
The loop condition for node != nil guards each node.value read. On equality the function returns true; otherwise target < node.value moves to node.left, and the else branch moves to node.right.
The trace starts from 4(2(1,3),6(5,7)). Searching 5 visits cursor 4 and branches right, visits 6 and branches left, then matches at 5.
Searching 8 visits 4, 6, and 7, branches right each time, then reaches a nil cursor and returns false. This lesson has no separate imbalance or degradation contrast; the checked trace only shows the balanced-tree miss path.
main formats results with string literals around the boolean return: fmt.Println("5 found") and fmt.Println("8 not found"), producing the two-line output 5 found / 8 not found.