bst.rb

#!/usr/bin/env ruby
# bst is O(log(n))        # the inverse is O(n^2))
# Almost, the inverse of 2^n is log2(n)
# define Node with pointers left and right and data key|value pair
p Node = Struct.new(:data, :left, :right)
puts

# define tree having root and current 
class Tree
  attr_accessor :root

  # the root node's .data will be nil, the node won't be nil
    # root.data == nil initiall
    # root will be nil once, if creating the tree
  def initialize
    self.root = Node.new
  end

  # if data is less than current.data, go left, else go right.
  def append(data)
    append_to_node(root, data)
  end

  private
  def append_to_node(current_node, data)
    # we check if node passed in should go left or right, based on data being larger or smaller than before
    # if data passed in is larger than current_node.data 
    if current_node.data.nil?
      current_node.data = data
    else
      if data > current_node.data # go right    # treeTest.rb:28:in `>': comparison of String with nil failed (ArgumentError)
        # and if right is not nil
        if current_node.right != nil
          # then need to traverse down towards right
          # recursively by calling this append_to_node method again
          # passing in current_node.right pointer as current, and same data
          append_to_node(current_node.right, data)
        else # we dont need to traverse we just append
          current_node.data = data
        end
      else
        if current_node.left != nil
          append_to_node(current_node.left, data)
        else
          current_node.data = data
        end
      end
    end
  end
end

p tree = Tree.new

# append new node to tree
p tree.append("j")
p tree.append("a")
p tree.append("s")
p tree.append("o")
p tree.append("n")