Trees

BST Search

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

Algorithm

Basic Implementation

basic.rb 
class Node
  attr_accessor :value, :left, :right
  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
end
def render(node)
  return "_" if node.nil?
  return node.value.to_s if node.left.nil? && node.right.nil?
  "#{node.value}(#{render(node.left)},#{render(node.right)})"
end
def sample_tree
  Node.new(4, Node.new(2, Node.new(1), Node.new(3)), Node.new(6, Node.new(5), Node.new(7)))
end
def search(root, target); node = root; until node.nil?; return true if target == node.value; node = target < node.value ? node.left : node.right; end; false; end
root = sample_tree
puts(search(root, 5) ? '5 found' : '5 not found')
puts(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

  • Node is a Ruby class with mutable value, left, and right accessors, matching the insert lesson's object shape.
  • Empty child links are nil, and the search loop stops with until node.nil?.
  • search(root, target) uses a local cursor, node = root, rather than recursion.
  • Each loop checks return true if target == node.value before choosing a child link.
  • If the target is smaller, the cursor moves to node.left; otherwise it moves to node.right.
  • The trace for 5 walks 4 -> right, 6 -> left, then matches at 5.
  • The trace for missing 8 walks 4 -> right, 6 -> right, 7 -> right, then reaches nil and returns false.
  • The checked output formats the two Boolean results as 5 found and 8 not found.
search path A comparison chooses one subtree at each step, so whole branches are skipped.