Basic Stuff for Trees

Trees.rb

#################TREES############
# The TreeNode Class
class Node
  attr_accessor :left, :right, :val
  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end
end

# create an example tree
a = Node.new(1)
b = Node.new(2)
c = Node.new(3)
d = Node.new(4)
e = Node.new(5)

a.left = b
a.right = c
c.right = e
c.left = d
head = a

# preorder traversal
def preorder(root)
  return if root.nil?
  puts root.val
  preorder(root.left)
  preorder(root.right)
end
preorder(head)

# postorder traversal
def postorder(root)
  return if root.nil?
  postorder(root.left)
  postorder(root.right)
  puts root.val
end
postorder(head)

# inorder traversal
def inorder(root)
  return if root.nil?
  [inorder(root.left),
  root.val,
  inorder(root.right)].flatten
end
inorder(head)

# DFS in Binary Tree
def dfs(root, val)
  return false if root.nil?
  return true if val == root.val
  return dfs(root.left, val) || dfs(root.right, val)
end
dfs(head,5)

#BFS in a Binary Tree is implemented by visiting all siblings at every level using a Queue
def bfs(root, val)
  q = []
  q.push(root)
  while(!q.is_empty)
    node = q.shift
    return true if val == node.val
    q.push(node.left) if node.left
    q.push(node.right) if node.right
  end
  false
end
bfs(head,5)