Skip to content

Instantly share code, notes, and snippets.

@prat0318
Created March 19, 2014 07:39
Show Gist options
  • Save prat0318/9637100 to your computer and use it in GitHub Desktop.
Save prat0318/9637100 to your computer and use it in GitHub Desktop.
class TreeNode
attr_accessor :left
attr_accessor :right
attr_reader :value
def initialize(left, right, value)
@left = left
@right = right
@value = value
end
end
def init()
n31 = TreeNode.new(TreeNode.new(nil,nil,4), nil, 2)
n32 = TreeNode.new(nil, TreeNode.new(nil,nil,5), 3)
root = TreeNode.new(n31, n32, 1)
end
def print_level(node)
return [] if node.nil?
q = [node]
result = []
until q.empty?
pop = q.shift
result.push(pop.value)
q.push(pop.left) unless pop.left.nil?
q.push(pop.right) unless pop.right.nil?
end
result
end
class Node
attr_accessor :left, :right
attr_reader :val
def initialize(val)
@val = val
end
end
class BST
def insert(val)
if(@root.nil?)
@root = Node.new(val)
else
insert_at(@root, Node.new(val))
end
end
def insert_at(sub_root, node)
if(sub_root.val > node.val)
if(sub_root.left.nil?)
sub_root.left = node
else
insert_at(sub_root.left, node)
end
else
if(sub_root.right.nil?)
sub_root.right = node
else
insert_at(sub_root.right, node)
end
end
end
def insert_at_alt(sub_root, node)
if(sub_root.nil?)
return node
elsif(sub_root.val > node.val)
sub_root.left = insert_at(sub_root.left, node)
else
sub_root.right = insert_at(sub_root.right, node)
end
return sub_root
end
def print(node = @root)
if(node.nil?)
puts("Tree empty!")
else
print(node.left) unless node.left.nil?
puts(node.val)
print(node.right) unless node.right.nil?
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment