Trees

BST Search

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

Algorithm

Basic Implementation

basic.swift 
final class Node {
    let value: Int
    var left: Node?
    var right: Node?
    init(_ value: Int, _ left: Node? = nil, _ right: Node? = nil) { self.value = value; self.left = left; self.right = right }
}
func render(_ node: Node?) -> String {
    guard let node = node else { return "_" }
    if node.left == nil && node.right == nil { return String(node.value) }
    return "\(node.value)(\(render(node.left)),\(render(node.right)))"
}
func sampleTree() -> Node {
    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
}
func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }
func search(_ root: Node?, _ target: Int) -> Bool { var node = root; while let current = node { if target == current.value { return true }; node = target < current.value ? current.left : current.right }; return false }
let root = sampleTree()
print(search(root, 5) ? "5 found" : "5 not found")
print(search(root, 8) ? "8 found" : "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

  • final class Node gives the tree reference semantics; each node has a let value: Int and mutable optional child links left: Node? and right: Node?.
  • sampleTree() builds the checked tree directly with nested Node(...) calls: 4(2(1,3),6(5,7)).
  • search(_ root: Node?, _ target: Int) -> Bool is iterative. It starts with var node = root and uses while let current = node to unwrap each cursor.
  • A match returns true immediately. Otherwise the cursor moves with target < current.value ? current.left : current.right.
  • When the cursor becomes nil, the loop ends and the function returns false; there is no numeric sentinel in this source.
  • The trace for 5 walks 4 -> right, 6 -> left, then matches at 5.
  • The trace for 8 walks 4 -> right, 6 -> right, 7 -> right, then reaches null for the not-found result; this replay uses the balanced sample tree and does not include an imbalance contrast event.
  • The two print calls use ternary formatting, producing exactly 5 found and 8 not found on separate lines.
search path A comparison chooses one subtree at each step, so whole branches are skipped.