1#!/usr/bin/env ruby
  2
  3def assert_equal(x, y)
  4  raise "expected: #{x.inspect}, actual: #{y.inspect}" unless x == y
  5end
  6
  7class Node
  8  attr_reader :value, :left, :right
  9
 10  def initialize(value, left = nil, right = nil)
 11    @value = value
 12    @left = left
 13    @right = right
 14  end
 15
 16  def inspect
 17    "(#{value}, #{left.inspect}, #{right.inspect})"
 18  end
 19end
 20
 21
 22def find_subtree(s, t)
 23  puts [s&.value, t&.value].inspect if ENV['DEBUG']
 24
 25  return t.nil? if s.nil?
 26  return s.nil? if t.nil?
 27
 28  if s.value == t.value
 29    return find_subtree(s.right, t.right) if s.left.nil?
 30    return find_subtree(s&.left, t&.left) if s.right.nil?
 31    return find_subtree(s&.left, t&.left) && find_subtree(s.right, t.right)
 32  end
 33
 34  return find_subtree(s, t&.left) || find_subtree(s, t&.right)
 35end
 36
 37
 38t = Node.new(
 39  1,
 40  Node.new(
 41    5,
 42    Node.new(4),
 43    Node.new(-1)
 44  ),
 45  Node.new(
 46    4,
 47    Node.new(3),
 48    Node.new(2)
 49  )
 50)
 51s = Node.new(
 52  4,
 53  Node.new(3),
 54  Node.new(2)
 55)
 56
 57assert_equal(true, find_subtree(s, t))
 58
 59t = Node.new(
 60  1,
 61  Node.new(
 62    5,
 63    Node.new(4),
 64    Node.new(-1)
 65  ),
 66  Node.new(
 67    4,
 68    Node.new(3),
 69    Node.new(2)
 70  )
 71)
 72s = Node.new(
 73  5,
 74  Node.new(4),
 75  Node.new(-1)
 76)
 77assert_equal(true, find_subtree(s, t))
 78
 79t = Node.new(
 80  1,
 81  Node.new(
 82    5,
 83    Node.new(4),
 84    Node.new(-1)
 85  ),
 86  Node.new(
 87    4,
 88    Node.new(3),
 89    Node.new(2)
 90  )
 91)
 92s = Node.new(3)
 93assert_equal(true, find_subtree(s, t))
 94
 95t = Node.new(
 96  1,
 97  Node.new(
 98    5,
 99    Node.new(4),
100    Node.new(-1)
101  ),
102  Node.new(
103    4,
104    Node.new(3),
105    Node.new(2)
106  )
107)
108s = Node.new(2)
109assert_equal(true, find_subtree(s, t))
110
111t = Node.new(
112  1,
113  Node.new(
114    5,
115    Node.new(4),
116    Node.new(-1)
117  ),
118  Node.new(
119    4,
120    Node.new(3),
121    Node.new(2)
122  )
123)
124s = Node.new(
125  1,
126  Node.new(
127    5,
128    Node.new(4),
129    Node.new(-1)
130  ),
131  Node.new(
132    4,
133    Node.new(3),
134    Node.new(2)
135  )
136)
137assert_equal(true, find_subtree(s, t))
138
139t = Node.new(
140  1,
141  Node.new(
142    5,
143    Node.new(4),
144    Node.new(-1)
145  ),
146  Node.new(
147    4,
148    Node.new(3),
149    Node.new(2)
150  )
151)
152s = Node.new(
153  1,
154  Node.new(
155    5,
156    nil,
157    Node.new(-1)
158  ),
159)
160assert_equal(true, find_subtree(s, t))
161
162
163t = Node.new(
164  1,
165  Node.new(
166    5,
167    Node.new(4),
168  ),
169  Node.new(
170    4,
171    Node.new(3),
172    Node.new(2)
173  )
174)
175s = Node.new(
176  1,
177  Node.new(
178    5,
179    Node.new(4),
180    Node.new(-1)
181  ),
182  Node.new(
183    4,
184    Node.new(3),
185    Node.new(2)
186  )
187)
188
189assert_equal(false, find_subtree(s, t))
190
191assert_equal(false, find_subtree(nil, t))