Implementing a Binary Search Tree in Ruby

A binary search tree keeps a simple invariant:

• every value in the left subtree is smaller than the node;
• every value in the right subtree is greater than the node.

That invariant—not the presence of left and right variables—is what makes searching efficient.

Implementation

class BinarySearchTree
  Node = Data.define(:value, :left, :right)

  attr_reader :root

  def insert(value)
    @root = insert_node(root, value)
    self
  end

  def include?(value)
    current = root

    while current
      return true if value == current.value
      current = value < current.value ? current.left : current.right
    end

    false
  end

  def each_in_order(&block)
    return enum_for(__method__) unless block

    traverse_in_order(root, &block)
    self
  end

  def max_depth
    depth(root)
  end

  private

  def insert_node(node, value)
    return Node.new(value:, left: nil, right: nil) unless node
    return node if value == node.value

    if value < node.value
      Node.new(value: node.value, left: insert_node(node.left, value), right: node.right)
    else
      Node.new(value: node.value, left: node.left, right: insert_node(node.right, value))
    end
  end

  def traverse_in_order(node, &block)
    return unless node

    traverse_in_order(node.left, &block)
    block.call(node.value)
    traverse_in_order(node.right, &block)
  end

  def depth(node)
    return 0 unless node

    1 + [depth(node.left), depth(node.right)].max
  end
end

Usage:

tree = BinarySearchTree.new
[8, 3, 10, 1, 6, 14].each { |value| tree.insert(value) }

tree.include?(6)       # => true
tree.each_in_order.to_a # => [1, 3, 6, 8, 10, 14]
tree.max_depth          # => 3

Why there is no direct update

Changing a node value in place can violate the ordering invariant. Updating 3 to 100 while leaving it in the left subtree makes future search results wrong. A safe update is delete plus insert, or rebuilding the affected structure.

Complexity

For a balanced tree, search and insert are O(log n). For a badly skewed tree, both degrade to O(n)—a linked list wearing a tree costume.

Production containers use balancing strategies such as AVL or red-black trees when worst-case behavior matters. This implementation is deliberately unbalanced because its job is to expose the invariant, not to impersonate a standard library.

Data.define requires modern Ruby. On older Ruby versions, replace it with Struct.new(:value, :left, :right, keyword_init: true).