Binary Search Tree w/out Recursion

binary_tree.rb

The "BST In-Order Traversal" Problem

Given a binary search tree, produce an in-order list of all keys in the tree without using recursion.
Explain and code an efficient solution. Analyze the time and space complexities.

Follow Up Problem:
Same problem as above but this time you also can't use a stack or any additional memory besides the tree.

class BinarySearchTree
  attr_accessor :data, :left, :right

  def initialize(data)
    @data = data
  end

  def insert(data)
    if @data < data
      if @right.nil?
        @right = BinarySearchTree.new(data)
      else
        @right.insert(data)
      end
    else
      if @left.nil?
        @left = BinarySearchTree.new(data)
      else
        @left.insert(data)
      end
    end
  end

  def each(&block)
    BinarySearchTree.traverse_preorder(&block)
  end

  def self.traverse_preorder(node, &block)
    node.left.traverse_preorder(&block)
    blk.call(node.data)
    node.right.traverse_preorder(&block)
  end
end