BST Search - Ruby DSA

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Ruby 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.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')

                        

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.