http://dandreamsofcoding.com/2014/03/18/dissecting-an-interview-question/

bst_insert.py

class TreeNode
  attr_accessor :left
  attr_accessor :right
  attr_reader :value

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

def init()
  n31 = TreeNode.new(TreeNode.new(nil,nil,4), nil, 2)
  n32 = TreeNode.new(nil, TreeNode.new(nil,nil,5), 3)
  root = TreeNode.new(n31, n32, 1)
end

def print_level(node)
  return [] if node.nil?
  q = [node]
  result = []
  until q.empty?
    pop = q.shift
    result.push(pop.value)
    q.push(pop.left) unless pop.left.nil?
    q.push(pop.right) unless pop.right.nil?
  end
  result
end

bst_insert1.rb

class Node
  attr_accessor :left, :right
  attr_reader :val

  def initialize(val)
    @val = val
  end
end

class BST

  def insert(val)
    if(@root.nil?)
      @root = Node.new(val)
    else
      insert_at(@root, Node.new(val))
    end
  end

  def insert_at(sub_root, node)
    if(sub_root.val > node.val)
      if(sub_root.left.nil?)
        sub_root.left = node
      else
        insert_at(sub_root.left, node)
      end
    else
      if(sub_root.right.nil?)
        sub_root.right = node
      else
        insert_at(sub_root.right, node)
      end
    end
  end

  def insert_at_alt(sub_root, node)
    if(sub_root.nil?)
      return node
    elsif(sub_root.val > node.val)
      sub_root.left = insert_at(sub_root.left, node)
    else
      sub_root.right = insert_at(sub_root.right, node)
    end
    return sub_root
  end
  
  def print(node = @root)
    if(node.nil?)
      puts("Tree empty!")
    else
      print(node.left) unless node.left.nil?
      puts(node.val)
      print(node.right) unless node.right.nil?
    end
  end
end