dfs

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

class TreeNode
  attr_reader :data, :subtrees
  private :data, :subtrees

  def initialize(data:, subtrees:[])
    @data = data
    @subtrees = subtrees
  end

  # returns an empty node if search_key is not found in tree
  def dfs(search_key)
    return self if search_key == data
    subtrees.each do |tree|
      tree_search = tree.dfs(search_key)
      return tree_search unless tree_search.empty?
    end
    EmptyNode.new
  end

  def empty?
    false
  end
end

class EmptyNode
  def dfs(search_key)
    self
  end

  def empty?
    true
  end
end

sample = TreeNode.new(data: "a", subtrees: [
  TreeNode.new(data: "b", subtrees: [
    TreeNode.new(data: "d", subtrees: []),
    TreeNode.new(data: "e", subtrees: []),
    TreeNode.new(data: "f", subtrees: [])
  ]),
  TreeNode.new(data: "c", subtrees: [
    TreeNode.new(data: "g", subtrees: [
      TreeNode.new(data: "h", subtrees: [])
    ])
  ])
])

p sample.dfs("d")