#!/usr/bin/env ruby

def assert_equal(x, y)
  raise "expected: #{x.inspect}, actual: #{y.inspect}" unless x == y
end

class Node
  attr_reader :value, :left, :right

  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end

  def inspect
    "(#{value}, #{left.inspect}, #{right.inspect})"
  end
end


def find_subtree(s, t)
  puts [s&.value, t&.value].inspect if ENV['DEBUG']

  return t.nil? if s.nil?
  return s.nil? if t.nil?

  if s.value == t.value
    return find_subtree(s.right, t.right) if s.left.nil?
    return find_subtree(s&.left, t&.left) if s.right.nil?
    return find_subtree(s&.left, t&.left) && find_subtree(s.right, t.right)
  end

  return find_subtree(s, t&.left) || find_subtree(s, t&.right)
end


t = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
s = Node.new(
  4,
  Node.new(3),
  Node.new(2)
)

assert_equal(true, find_subtree(s, t))

t = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
s = Node.new(
  5,
  Node.new(4),
  Node.new(-1)
)
assert_equal(true, find_subtree(s, t))

t = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
s = Node.new(3)
assert_equal(true, find_subtree(s, t))

t = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
s = Node.new(2)
assert_equal(true, find_subtree(s, t))

t = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
s = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
assert_equal(true, find_subtree(s, t))

t = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
s = Node.new(
  1,
  Node.new(
    5,
    nil,
    Node.new(-1)
  ),
)
assert_equal(true, find_subtree(s, t))


t = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)
s = Node.new(
  1,
  Node.new(
    5,
    Node.new(4),
    Node.new(-1)
  ),
  Node.new(
    4,
    Node.new(3),
    Node.new(2)
  )
)

assert_equal(false, find_subtree(s, t))

assert_equal(false, find_subtree(nil, t))