Trees

BST Search

Search a binary search tree for one present and one absent value.

Algorithm

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") } }

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.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

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

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot 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.
search path A comparison chooses one subtree at each step, so whole branches are skipped.