# Binary Search Trees

There's nothing like implementing some data structures on a Friday night! In my ongoing pursuit of shoring up my CS basics, I decided to take some time tonight reading up on Binary Search Trees, as many interview gotchas that I hear of seem to involve them. This is a fairly simple implementation with only the size, get, and put methods, but its a start.

``````class BinarySearchTree

def initialize(key, value)
@root = Node.new(key,value)
end

def size(node)
node.nil? ? 0 : size(node.left) + size(node.right) + 1
end

def get(node,key)
return nil if node.nil?
if node.key == key
node
else
key < node.key ? get(node.left, key) : get(node.right, key)
end
end

def put(node, key, value)
if node.key == key
puts "Changed Value of Node #{key} to #{value}"
return node.value = value
end

if key < node.key
if node.left
put(node.left,key,value)
else
puts "Added a new node to the left of #{node} with key #{key}, value #{value}"
node.left = Node.new(key,value)
end
else
if node.right
put(node.right,key,value)
else
puts "Added a new node to the right of #{node} with key #{key}, value #{value}"
node.right= Node.new(key,value)
end
end
end

class Node
attr_accessor :left, :right, :key, :value

def initialize(key, value)
@key = key
@value = value
end
end
end
``````

And to try it out in the wild, heres a little implementation script.

``````nums = (1..100000).to_a.shuffle
bst = BinarySearchTree.new(nums.pop, 5)
b = bst.root

until nums.empty? do
bst.put(b, nums.pop, (1..9).to_a.sample)
end
``````

Lets benchmark searching for a number in this tree we made with searching for one in an array to see the benefit of BSTs.

``````require 'benchmark'
nums = (1..100000).to_a.shuffle # need to remake as we destroyed it via pop
Benchmark.bm do |benchmark|
benchmark.report("array search"){ (1..10000).each {|n| nums.include? n } }
benchmark.report("binary tree "){ (1..10000).each {|n| bst.get(b, n) } }
end

user     system      total        real
array search  3.090000   0.000000   3.090000 (  3.102407)
binary tree   0.040000   0.000000   0.040000 (  0.038214)
``````

Pretty cool, that is quite a lot faster! Binary Trees are able to query in 2 ln N time, which is about 1.39 lg N.

-JM