master
1<<-DOC
2Given two binary trees t1 and t2, determine whether the second one is a subtree of the first one.
3A subtree for vertex v in binary tree t is a tree consisting of v and all its descendants in t.
4Your task is to check whether there is a vertex v in tree t1 such that a subtree for vertex v in t1 equals t2.
5
6Example
7
8For
9
10t1 = {
11 value: 5,
12 left: {
13 value: 10,
14 left: {
15 value: 4,
16 left: {
17 value: 1,
18 left: null,
19 right: null
20 },
21 right: {
22 value: 2,
23 left: null,
24 right: null
25 }
26 },
27 right: {
28 value: 6,
29 left: null,
30 right: {
31 value: -1,
32 left: null,
33 right: null
34 }
35 }
36 },
37 right: {
38 value: 7,
39 left: null,
40 right: null
41 }
42}
43and
44
45t2 = {
46 value: 10,
47 left: {
48 value: 4,
49 left: {
50 value: 1,
51 left: null,
52 right: null
53 },
54 right: {
55 value: 2,
56 left: null,
57 right: null
58 }
59 },
60 right: {
61 value: 6,
62 left: null,
63 right: {
64 value: -1,
65 left: null,
66 right: null
67 }
68 }
69}
70the output should be isSubtree(t1, t2) = true.
71
72This is what these trees look like:
73
74 t1: t2:
75 5 10
76 / \ / \
77 10 7 4 6
78 / \ / \ \
79 4 6 1 2 -1
80 / \ \
811 2 -1
82As you can see, t2 is a subtree of t1 (the vertex in t1 with value 10).
83
84For
85
86t1 = {
87 value: 5,
88 left: {
89 value: 10,
90 left: {
91 value: 4,
92 left: {
93 value: 1,
94 left: null,
95 right: null
96 },
97 right: {
98 value: 2,
99 left: null,
100 right: null
101 }
102 },
103 right: {
104 value: 6,
105 left: {
106 value: -1,
107 left: null,
108 right: null
109 },
110 right: null
111 }
112 },
113 right: {
114 value: 7,
115 left: null,
116 right: null
117 }
118}
119and
120
121t2 = {
122 value: 10,
123 left: {
124 value: 4,
125 left: {
126 value: 1,
127 left: null,
128 right: null
129 },
130 right: {
131 value: 2,
132 left: null,
133 right: null
134 }
135 },
136 right: {
137 value: 6,
138 left: null,
139 right: {
140 value: -1,
141 left: null,
142 right: null
143 }
144 }
145}
146the output should be isSubtree(t1, t2) = false.
147
148This is what these trees look like:
149
150 t1: t2:
151 5 10
152 / \ / \
153 10 7 4 6
154 / \ / \ \
155 4 6 1 2 -1
156 / \ /
1571 2 -1
158As you can see, there is no vertex v such that the subtree of t1 for vertex v equals t2.
159
160For
161
162t1 = {
163 value: 1,
164 left: {
165 value: 2,
166 left: null,
167 right: null
168 },
169 right: {
170 value: 2,
171 left: null,
172 right: null
173 }
174}
175and
176
177t2 = {
178 value: 2,
179 left: {
180 value: 1,
181 left: null,
182 right: null
183 },
184 right: null
185}
186the output should be isSubtree(t1, t2) = false.
187
188Input/Output
189
190[time limit] 4000ms (rb)
191[input] tree.integer t1
192
193A binary tree of integers.
194
195Guaranteed constraints:
1960 ≤ tree size ≤ 6 · 104,
197-1000 ≤ node value ≤ 1000.
198
199[input] tree.integer t2
200
201Another binary tree of integers.
202
203Guaranteed constraints:
2040 ≤ tree size ≤ 6 · 104,
205-1000 ≤ node value ≤ 1000.
206
207[output] boolean
208
209Return true if t2 is a subtree of t1, otherwise return false.
210DOC
211describe "#subtree?" do
212 # (1(2(),3())
213 def to_sexpression(tree)
214 return "()" if tree.nil?
215 "(#{tree.value}#{to_sexpression(tree.left)},#{to_sexpression(tree.right)})"
216 end
217
218 def subtree?(t1, t2)
219 return true if (t1.nil? && t2.nil?) || (t1 && t2.nil?)
220 to_sexpression(t1).include?(to_sexpression(t2))
221 end
222
223 null = nil
224 [
225 { t1: { value: 5, left: { value: 10, left: { value: 4, left: { value: 1, left: null, right: null }, right: { value: 2, left: null, right: null } }, right: { value: 6, left: null, right: { value: -1, left: null, right: null } } }, right: { value: 7, left: null, right: null } }, t2: { value: 10, left: { value: 4, left: { value: 1, left: null, right: null }, right: { value: 2, left: null, right: null } }, right: { value: 6, left: null, right: { value: -1, left: null, right: null } } }, x: true },
226 { t1: { value: 5, left: { value: 10, left: { value: 4, left: { value: 1, left: null, right: null }, right: { value: 2, left: null, right: null } }, right: { value: 6, left: { value: -1, left: null, right: null }, right: null } }, right: { value: 7, left: null, right: null } }, t2: { value: 10, left: { value: 4, left: { value: 1, left: null, right: null }, right: { value: 2, left: null, right: null } }, right: { value: 6, left: null, right: { value: -1, left: null, right: null } } }, x: false },
227 { t1: { value: 1, left: { value: 2, left: null, right: null }, right: { value: 2, left: null, right: null } }, t2: { value: 2, left: { value: 1, left: null, right: null }, right: null }, x: false },
228 { t1: { value: 1, left: { value: 2, left: null, right: null }, right: { value: 2, left: null, right: null } }, t2: null, x: true },
229 { t1: null, t2: null, x: true },
230 { t1: null, t2: { value: 2, left: null, right: null }, x: false },
231 { t1: { value: 1, left: { value: 2, left: null, right: null }, right: { value: 2, left: null, right: null } }, t2: { value: 2, left: null, right: null }, x: true },
232 { t1: { value: 3, left: { value: 1 }, right: {} }, t2: null, x: true },
233 { t1: { value: 2, right: { value: 3 } }, t2: { value: 2, left: { value: 1 }, right: { value: 3 } }, x: false },
234 ].each do |x|
235 <<-DOC
236
237 2
238 \
239 3
240
241 2
242 / \
243 1 3
244
245 DOC
246 it do
247 expect(
248 subtree?(Tree.build_from(x[:t1]), Tree.build_from(x[:t2]))
249 ).to eql(x[:x])
250 end
251 end
252end