Find the kth smallest element in a binary tree

tree.rb

#!/bin/ruby

class Node
  attr_accessor :value
  attr_accessor :left
  attr_accessor :right

  def initialize(value)
    self.value = value
  end
end

def inorder(root)
  if not root.left.nil?
    inorder(root.left)
  end

  puts root.value

  if not root.right.nil?
    inorder(root.right)
  end
end

def ksmallest(root, k)
  l = []
  _ksmallest(root, k, l)
  l[k - 1]
end

def _ksmallest(root, k, l)
  if not root.left.nil?
    _ksmallest(root.left, k, l)
  end

  l << root.value

  if not root.right.nil?
    _ksmallest(root.right, k, l)
  end
end

def add(value, root)
  if root.nil?
    return Node.new(  value)
  else
    if value > root.value 
      if root.right.nil?
        root.right = Node.new(value)
      else
        add(value, root.right)
      end
    else
      if root.left.nil?
        root.left = Node.new(value)
      else
        add(value, root.left)
      end
    end
  end 
end

puts 'Program Start'

#       7
#   3      9
# 1   4

root = add(7, nil)
add(3, root)
add(4, root)
add(1, root)
add(9, root)

inorder(root)

n = ksmallest(root, 3)
puts "3rd smallest: #{n}"