Skip to content

Instantly share code, notes, and snippets.

@sumanmukherjee03
Created May 24, 2013 19:29
Show Gist options
  • Save sumanmukherjee03/5645949 to your computer and use it in GitHub Desktop.
Save sumanmukherjee03/5645949 to your computer and use it in GitHub Desktop.
Implementation of preorder, inorder and postorder in a binary tree
require 'rspec'
require 'forwardable'
RSpec.configure do |config|
config.mock_with :rspec
config.color_enabled = true
end
class Node
def initialize(value)
@left = nil
@right = nil
@value = value
end
def add_left(value)
@left = Node.new(value)
end
def add_right(value)
@right = Node.new(value)
end
def inorder
[(@left.inorder if @left), @value, (@right.inorder if @right)].flatten.compact
end
def preorder
[@value, (@left.preorder if @left), (@right.preorder if @right)].flatten.compact
end
def postorder
[(@left.postorder if @left), (@right.postorder if @right), @value].flatten.compact
end
end
class BinaryTree
extend Forwardable
attr_reader :root
def_delegators :"@root", :inorder, :preorder, :postorder
def initialize(root_value)
@root = Node.new(root_value)
end
end
describe BinaryTree do
subject { BinaryTree.new(4) }
before do
node_2 = subject.root.add_left(2)
node_2.add_left(1)
node_2.add_right(3)
node_6 = subject.root.add_right(6)
node_6.add_left(5)
node_6.add_right(7)
end
describe "#inorder" do
it "return node values" do
subject.inorder.should eq([1, 2, 3, 4, 5, 6, 7])
end
end
describe "#preorder" do
it "return node values" do
subject.preorder.should eq([4, 2, 1, 3, 6, 5, 7])
end
end
describe "#postorder" do
it "return node values" do
subject.postorder.should eq([1, 3, 2, 5, 7, 6, 4])
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment