Algorithmathon Day 9: Trees Base

Created: 23 July 2013  Modified:

The goal for today is to setup the basics for trees. The basic object for trees is the node. A node is a collection of references/pointers to other nodes. Lets write the tests and code to satisfy this requirement. I will be concentrating on the BinarySearchTreeNode object. You will find a TreeNode and a BinaryTreeNode in the code on GitHub.

binary_search_tree_node_spec.rb

require 'spec_helper'

describe BinarySearchTreeNode do

  describe "Class" do
    it "should have method 'greater'" do
      BinarySearchTreeNode.method_defined?(:greater).should be_true
    end

    it "should have method 'lesser'" do
      BinarySearchTreeNode.method_defined?(:lesser).should be_true
    end 

     it "should have method 'data'" do
      BinarySearchTreeNode.method_defined?(:data).should be_true
    end 

    it "should have method 'less_than?'" do
      BinarySearchTreeNode.method_defined?(:less_than?).should be_true
    end     

    it "should have method 'greater_than?'" do
      BinarySearchTreeNode.method_defined?(:greater_than?).should be_true
    end     
  end

  describe "Instance" do

    before(:each) do
      @node = BinarySearchTreeNode.new(5)
    end

    it "should not be nil" do
      @node.should_not be_nil
    end

    it "should not throw an exeption because greater, lesser and parent are nil" do
      expect {parent = BinarySearchTreeNode.new(5)}.to_not raise_error
    end

    it "should throw an exeption because lesser is more than greater" do
      lesser = BinarySearchTreeNode.new(10)
      greater = BinarySearchTreeNode.new(5)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end

    it "should throw an exeption because lesser is not nil and greater is" do
      lesser = BinarySearchTreeNode.new(10)
      expect { parent = BinarySearchTreeNode.new(7,lesser) }.to raise_error
    end

    it "should not throw an exeption because lesser is less than greater" do
      lesser = BinarySearchTreeNode.new(5)
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to_not raise_error
    end

    it "should not throw an exeption because lesser is nil and greater is not" do
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,nil,greater)}.to_not raise_error
    end    

    it "should not throw an exeption because lesser and greater are nil" do
      expect {parent = BinarySearchTreeNode.new(7)}.to_not raise_error
    end    

    it "should throw an exeption because lesser and greater are equal" do
      lesser = BinarySearchTreeNode.new(10)
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end    

    it "should throw an exeption because lesser and parent are equal" do
      lesser = BinarySearchTreeNode.new(7)
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end

    it "should throw an exeption because greater and parent are equal" do
      lesser = BinarySearchTreeNode.new(3)
      greater = BinarySearchTreeNode.new(7)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end    

    it "should return true when lesser.lesser_than?(greater) is called" do
      lesser = BinarySearchTreeNode.new(3)
      greater = BinarySearchTreeNode.new(7)
      lesser.less_than?(greater).should be_true
    end    

    it "should return false when greater.greater_than?(lesser) is called" do
      lesser = BinarySearchTreeNode.new(3)
      greater = BinarySearchTreeNode.new(7)
      greater.greater_than?(lesser).should be_true
    end
  end

end

As can be seen we have added several tests that enforce the attributes that make a Binary Search Tree. With the code below to satisfy the tests we can move on to building a Binary Search Tree.

tree_node.rb

class BinarySearchTreeNode
  attr_accessor :lesser, :greater
  attr_reader :data

  def initialize(data,lesser=nil,greater=nil)
    @data=data
    self.lesser=lesser
    self.greater=greater
    if (!self.lesser.nil? && self.greater.nil?) || (!self.lesser.nil? && (self.lesser.data > self.greater.data))
      throw "The lesser exceeds the greater"
    end
   
    if !self.lesser.nil? && !self.data.nil? && self.lesser.data == self.data
      throw "The lesser is equal to the parent"
    end
    
    if !self.greater.nil? && !self.data.nil? && self.greater.data == self.data
      throw "The greater is equal to the parent"
    end    
    
    if !self.lesser.nil? && !self.greater.nil? && self.lesser.data == self.greater.data
      throw "The lesser is equal to the parent"
    end
  end

  def less_than?(target_node)
    if target_node.nil?
      raise "The target_node is nil!"
    else
      if @data < target_node.data
        true
      else
        false
      end
    end
  end

  def greater_than?(target_node)
    if target_node.nil?
      raise "The target_node is nil!"
    else
      if @data > target_node.data
        true
      else
        false
      end
    end
  end 
end

What do we know about a binary search tree? We know that it needs a starting node know as the “root”. If we are going to be able to write algorithms against a tree we need to be able to build a tree. This means we need a “root” attribute and an “add” method. We should add several tests to specify the functionality we need. These tests come quite naturally if you use the Test Driven Development methodology.

binary_search_tree_spec.rb

require 'spec_helper'

describe BinarySearchTree do

  describe "Class" do
    it "should have method 'root'" do
      BinarySearchTree.method_defined?(:root).should be_true
    end

    it "should have method 'add'" do
      BinarySearchTree.method_defined?(:add).should be_true
    end    
  end

  describe "Instance" do

    before(:each) do
      @tree = BinarySearchTree.new()
    end

    it "should have node(5) as the root when passed into constructor" do
      node = BinarySearchTreeNode.new(5)
      tree = BinarySearchTree.new(node)
      tree.root.should_not be_nil
      tree.root.data.should == 5
    end

    it "should have node(6) as the root when add(node(5)) is called" do
      node = BinarySearchTreeNode.new(5)
      tree = BinarySearchTree.new()
      tree.add(node)
      tree.root.should_not be_nil
      tree.root.data.should == 5
    end    

    it "should have add(node(5)) as the lesser of the root" do
      node = BinarySearchTreeNode.new(5)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
      tree.add(node)
      tree.root.lesser.should_not be_nil
      tree.root.lesser.data.should == 5
    end

    it "should have add(node(15)) as the greater of the root" do
      node = BinarySearchTreeNode.new(15)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
      tree.add(node)
      tree.root.greater.should_not be_nil
      tree.root.greater.data.should == 15
    end 

    it "should have add(node(10)) raise an error" do
      node = BinarySearchTreeNode.new(10)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
      expect { tree.add(node) }.to raise_error
    end   

    it "should have add(node(50)) as the lesser of the root.lesser" do
      node1 = BinarySearchTreeNode.new(75)
      node2 = BinarySearchTreeNode.new(50)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.add(node2)
      tree.root.lesser.should_not be_nil
      tree.root.lesser.lesser.should_not be_nil
      tree.root.lesser.lesser.data.should == 50
    end

    it "should have add(node(85)) as the greater of the root.lesser" do
      node1 = BinarySearchTreeNode.new(75)
      node2 = BinarySearchTreeNode.new(85)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.add(node2)
      tree.root.lesser.should_not be_nil
      tree.root.lesser.greater.should_not be_nil
      tree.root.lesser.greater.data.should == 85
    end 

     it "should have add(node(150)) as the greater of the root" do
      node1 = BinarySearchTreeNode.new(150)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.root.greater.should_not be_nil
      tree.root.greater.data.should == 150
    end 

     it "should return 125 when it recieves the root.greater.lesser.data call" do
      node1 = BinarySearchTreeNode.new(150)
      node2 = BinarySearchTreeNode.new(75)
      node3 = BinarySearchTreeNode.new(125)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.add(node2)
      tree.add(node3)
      tree.root.greater.should_not be_nil
      tree.root.greater.lesser.should_not be_nil
      tree.root.greater.lesser.data.should == 125
    end

  end

end

binary_search_tree.rb

class BinarySearchTree
  attr_reader :root

  def initialize(root=nil)
    @root=root
  end

  def add(new_node)
    if new_node.nil?
      new_node
    else
      if @root.nil?
        @root = new_node
      else
        add_by_recursion(@root,new_node)
      end
    end
  end

  private

  def add_by_recursion(current_node,new_node)
    if current_node.nil?
      current_node
    else
      if current_node.greater_than?(new_node)
        if current_node.lesser.nil?
          current_node.lesser=new_node
        else
          add_by_recursion(current_node.lesser,new_node)
        end            
      elsif current_node.less_than?(new_node)
        if current_node.greater.nil?
          current_node.greater=new_node
        else
          add_by_recursion(current_node.greater,new_node)
        end
      else
        raise "Node matches existing node" + new_node.data.to_s
      end 
    end
  end

end

We now have a Binary Search Tree with enough basic functionality to make it useful. Tomorrow we will look into depth first searches.

tags: Algorithm - Algorithmathon - RSpec - Ruby - Trees
   Less Is More