#!/usr/bin/env ruby
require 'pry'

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

  class << self
    def dfs(node, results = [])
      if node
        results << node.val
        dfs(node.left, results)
        dfs(node.right, results)
      end
      return results
    end

    def bft(node)
      results = []
      queue = [node]
      while queue.any? do
        curr = queue.shift
        return results unless curr
        results << curr.val
        queue = queue + [curr.left, curr.right]
      end
      results
    end
  end
end

require 'minitest/autorun'

describe Node do
  before do
    @root = Node.new(0)
    @root.left = Node.new(1)
    @root.right = Node.new(2)
    @root.left.left = Node.new(3)
    @root.left.right = Node.new(4)
    @root.right.left = Node.new(5)
    @root.right.right = Node.new(6)
  end

  describe 'dfs' do
    it "should traverse the tree" do
      result = Node.dfs(@root)
      result.must_equal([0,1,3,4,2,5,6])
    end
  end

  describe 'bft' do
    it "should traverse the tree" do
      result = Node.bft(@root)
      result.must_equal([0,1,2,3,4,5,6])
    end
  end
end