tree_traversal.rb

# reference: https://rlafranchi.github.io/2017/03/08/tree-traversal-for-rubyists/
# http://alrightchiu.github.io/SecondRound/binary-tree-traversalxun-fang.html

class Node
  attr_accessor :left, :right
  attr_reader :val
  def initialize(val)
    @val = val
  end
end

## Build the tree
# Visual Aid w/ indices of results:
#      I            0
#     / \          / \
#    O   H        1   6
#   / \ / \      / \ / \
#  L  R T  M    2  5 7  8
# / \          / \
#A   G        3   4
root = Node.new("I")

# first level
root.left = Node.new("O")
root.right = Node.new("H")

# second level
root.left.left = Node.new("L")
root.left.right = Node.new("R")
root.right.left = Node.new("T")
root.right.right = Node.new("M")

# third level
root.left.left.left = Node.new("A")
root.left.left.right = Node.new("G")

## Traversal
# VLR
def pre_order(node)
  return [] if node.nil?

  result = []
  result << node.val
  result.concat pre_order(node.left)
  result.concat pre_order(node.right)
  result#.flatten
end

# LVR
def in_order(node)
  return [] if node.nil?

  result = []
  result.concat in_order(node.left)
  result << node.val
  result.concat in_order(node.right)
  result
end

# LRV
def post_order(node)
  return [] if node.nil?

  result = []
  result.concat post_order(node.left)
  result.concat post_order(node.right)
  result << node.val
  result
end

## BFS
def breadth_first_search(node)
  return [] if node.nil?
  queue = []
  result = []

  queue.push node
  while !queue.empty?
    current_node = queue.shift
    queue.push current_node.left if current_node.left != nil
    queue.push current_node.right if current_node.right != nil
    result << current_node.val
  end
  result
end
## DFS


# p "# pre_order"
# p pre_order(root)
# p pre_order(root) == ["I", "O", "L", "A", "G", "R", "H", "T", "M"]
# p "# in_order"
# p in_order(root)
# p in_order(root) == ["A", "L", "G", "O", "R", "I", "T", "H", "M"]
# p "# post_order"
# p post_order(root)
# p post_order(root) == ["A", "G", "L", "R", "O", "T", "M", "H", "I"]

def expect(method, arg, ans)
  p "# #{method}"
  p send(method, arg)
  p send(method, arg) == ans
end

expect(:pre_order, root, ["I", "O", "L", "A", "G", "R", "H", "T", "M"])
expect(:in_order, root, ["A", "L", "G", "O", "R", "I", "T", "H", "M"])
expect(:post_order, root, ["A", "G", "L", "R", "O", "T", "M", "H", "I"])
expect(:breadth_first_search, root, ["I", "O", "H", "L", "R", "T", "M", "A", "G"])