How to create a binary search tree in Ruby

A binary search tree (BST) is a binary tree data structure where each node has at most two child nodes, arranged in a way that the value of the node to the left is less than or equal to the parent node, and the value of the node to the right is greater than or equal to the parent node. This property ensures that a binary search can be run on the tree, providing an efficient way to search, insert, and delete elements.

Here's a simple implementation of a binary search tree in Ruby:

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class BinarySearchTree
  def initialize
    @root = nil
  end

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

  def search(value)
    search_node(@root, value)
  end

  private

  def insert_node(node, value)
    return Node.new(value) if node.nil?

    if value <= node.value
      node.left = insert_node(node.left, value)
    else
      node.right = insert_node(node.right, value)
    end

    node
  end

  def search_node(node, value)
    return false if node.nil?

    if value == node.value
      true
    elsif value < node.value
      search_node(node.left, value)
    else
      search_node(node.right, value)
    end
  end
end

# Usage
bst = BinarySearchTree.new
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)

puts bst.search(40) # Output: true
puts bst.search(25) # Output: false

In this example, we define two classes: Node and BinarySearchTree. The Node class represents a node in the binary search tree and has attributes for its value and its left and right children. The BinarySearchTree class manages the tree and provides methods for inserting and searching elements in the tree.

The insert method of the BinarySearchTree class inserts a new value into the tree by calling the insert_node private method, which takes a node and a value as its arguments. If the node is nil, it creates a new node with the given value. Otherwise, it compares the value to the current node's value and inserts it either into the left subtree if the value is less than or equal to the current node's value or into the right subtree if the value is greater than the current node's value.

The search method of the BinarySearchTree class searches for a value in the tree by calling the search_node private method. This method recursively traverses the tree, checking whether the value matches the current node's value, or whether it should search in the left subtree (if the value is less than the current node's value) or the right subtree (if the value is greater than the current node's value). If the value is not found in the tree, it returns false.