TestBinarySearchTree.cxx File Reference
#include <gtest/gtest.h>
#include <binary_search_tree.hxx>
#include <functional>
#include <list>
Include dependency graph for TestBinarySearchTree.cxx:

Go to the source code of this file.

Functions

 TEST (TestBST, build)
 
 TEST (TestBST, buildFromSorted)
 
 TEST (TestBST, isValid)
 
 TEST (TestBST, AppendTree)
 
 TEST (TestBST, Size)
 
 TEST (TestBST, MinHeight)
 
 TEST (TestBST, MaxHeight)
 
 TEST (TestBST, IsBalanced)
 
 TEST (TestBST, Find)
 
 TEST (TestBST, Remove)
 

Function Documentation

TEST ( TestBST  ,
build   
)

Definition at line 64 of file TestBinarySearchTree.cxx.

65 {
66  // Empty Array - No BST should be built
67  {
68  const Container kEmptyCollection = Container();
69  Const_Own_BST tree = Const_BST::Build(kEmptyCollection.begin(), kEmptyCollection.end());
70  EXPECT_FALSE(tree);
71  }
72 
73  // Begin After End - No BST should be built
74  {
75  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
76  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.end(), kSmallIntArray.begin());
77  EXPECT_FALSE(tree);
78  }
79 
80  // Unique element - Root should be created
81  {
82  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
83  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
84  EXPECT_EQ(2, tree->GetData());
85  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
86  EXPECT_TRUE(tree->GetRightChild() == nullptr);
87  }
88 
89  // Basic construction
90  {
91  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
92  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
93 
94  EXPECT_EQ(2, tree->GetData());
95  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
96  EXPECT_EQ(3, tree->GetRightChild()->GetData());
97  EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
98  EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
99  EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
100  EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
101  }
102 
103  // Basic construction
104  {
105  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
106  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
107 
108  EXPECT_EQ(2, tree->GetData());
109  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
110  EXPECT_EQ(3, tree->GetRightChild()->GetData());
111  EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
112  EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
113  EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
114  EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
115  }
116 }
TEST ( TestBST  ,
buildFromSorted   
)

Definition at line 119 of file TestBinarySearchTree.cxx.

120 {
121  // Empty Array - No BST should be built
122  {
123  const Container kEmptyCollection = Container();
124  Const_Own_BST tree = Const_BST::Build(kEmptyCollection.begin(), kEmptyCollection.end());
125  EXPECT_FALSE(tree);
126  }
127 
128  // Begin After End - No BST should be built
129  {
130  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
131  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.end(), kSmallIntArray.begin());
132  EXPECT_FALSE(tree);
133  }
134 
135  // Unique element - Root should be created
136  {
137  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
138  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
139  EXPECT_EQ(2, tree->GetData());
140  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
141  EXPECT_TRUE(tree->GetRightChild() == nullptr);
142  }
143 
144  // Basic construction on sorted array
145  {
146  const Container kSmallSorted(SmallIntArraySorted,
147  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
148  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
149 
150  EXPECT_EQ(2, tree->GetData());
151  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
152  EXPECT_EQ(3, tree->GetRightChild()->GetData());
153  EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
154  EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
155  EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
156  EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
157  }
158 }
TEST ( TestBST  ,
isValid   
)

Definition at line 161 of file TestBinarySearchTree.cxx.

162 {
163  // Unique element - Root should be created
164  {
165  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
166  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
167  EXPECT_TRUE(tree->IsValid());
168  }
169 
170  // Basic construction
171  {
172  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
173  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
174  EXPECT_TRUE(tree->IsValid());
175  }
176 
177  // Basic construction on sorted array
178  {
179  const Container kSmallSorted(SmallIntArraySorted,
180  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
181  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
182  EXPECT_TRUE(tree->IsValid());
183  }
184 
185  // Wrong construction on unsorted array
186  {
187  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
188  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallIntArray.begin(), kSmallIntArray.end());
189  EXPECT_FALSE(tree->IsValid());
190  }
191 
192  // Basic construction with negative values and dupplicates
193  {
194  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
195  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
196  EXPECT_TRUE(tree->IsValid());
197  }
198 }
TEST ( TestBST  ,
AppendTree   
)

Definition at line 201 of file TestBinarySearchTree.cxx.

202 {
203  // Test adding some element within the BST and its structure
204  {
205  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
206  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
207  EXPECT_EQ(2, tree->GetData());
208  tree->Insert(10);
209  EXPECT_EQ(10, tree->GetRightChild()->GetData());
210  tree->Insert(15);
211  EXPECT_EQ(15, tree->GetRightChild()->GetRightChild()->GetData());
212  tree->Insert(-10);
213  EXPECT_EQ(-10, tree->GetLeftChild()->GetData());
214  tree->Insert(0);
215  EXPECT_EQ(0, tree->GetLeftChild()->GetRightChild()->GetData());
216  }
217 }
TEST ( TestBST  ,
Size   
)

Definition at line 220 of file TestBinarySearchTree.cxx.

221 {
222  // Unique element - Root should be created
223  {
224  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
225  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
226  EXPECT_EQ(1, tree->Size());
227  }
228 
229  // Basic construction - 3
230  {
231  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
232  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
233  EXPECT_EQ(kSmallIntArray.size(), tree->Size());
234  }
235 
236  // Basic construction on sorted array
237  {
238  const Container kSmallSorted(SmallIntArraySorted,
239  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
240  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
241  EXPECT_EQ(kSmallSorted.size(), tree->Size());
242  }
243 
244  // Basic construction with negative values and dupplicates
245  {
246  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
247  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
248  EXPECT_EQ(kRandIntArray.size(), tree->Size());
249  }
250 }
TEST ( TestBST  ,
MinHeight   
)

Definition at line 253 of file TestBinarySearchTree.cxx.

254 {
255  // Unique element - Root should be created
256  {
257  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
258  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
259  EXPECT_EQ(1, tree->MinHeight());
260  }
261 
262  // Basic construction
263  {
264  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
265  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
266  EXPECT_EQ(2, tree->MinHeight());
267  }
268 
269  // Basic construction on sorted array
270  {
271  const Container kSmallSorted(SmallIntArraySorted,
272  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
273  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
274  EXPECT_EQ(2, tree->MinHeight());
275  }
276 
277  // Basic construction with negative values and dupplicates
278  {
279  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
280  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
281  EXPECT_EQ(2, tree->MinHeight());
282  }
283 }
TEST ( TestBST  ,
MaxHeight   
)

Definition at line 286 of file TestBinarySearchTree.cxx.

287 {
288  // Unique element - Root should be created
289  {
290  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
291  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
292  EXPECT_EQ(1, tree->MaxHeight());
293  }
294 
295  // Basic construction
296  {
297  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
298  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
299  EXPECT_EQ(2, tree->MaxHeight());
300  }
301 
302  // Basic construction on sorted array
303  {
304  const Container kSmallSorted(SmallIntArraySorted,
305  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
306  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
307  EXPECT_EQ(2, tree->MaxHeight());
308  }
309 
310  // Basic construction with negative values and dupplicates
311  {
312  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
313  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
314  EXPECT_EQ(6, tree->MaxHeight());
315  }
316 }
TEST ( TestBST  ,
IsBalanced   
)

Definition at line 319 of file TestBinarySearchTree.cxx.

320 {
321  // Unique element - Root should be created
322  {
323  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
324  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
325  EXPECT_TRUE(tree->IsBlanced());
326  }
327 
328  // Basic construction
329  {
330  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
331  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
332  EXPECT_TRUE(tree->IsBlanced());
333  }
334 
335  // Basic construction on sorted array
336  {
337  const Container kSmallSorted(SmallIntArraySorted,
338  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
339  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
340  EXPECT_TRUE(tree->IsBlanced());
341  }
342 
343  // Basic construction with negative values and dupplicates
344  {
345  const Container kSortedArrayInt(SortedArrayInt, SortedArrayInt + sizeof(SortedArrayInt) / sizeof(Value));
346  Const_Own_BST tree = Const_BST::Build(kSortedArrayInt.begin(), kSortedArrayInt.end());
347  EXPECT_FALSE(tree->IsBlanced());
348  }
349 }
TEST ( TestBST  ,
Find   
)

Definition at line 352 of file TestBinarySearchTree.cxx.

353 {
354  // Unique element - Unique element should be found - not others
355  {
356  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
357  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
358  EXPECT_EQ(2, tree->Find(2)->GetData());
359  EXPECT_FALSE(tree->Find(0));
360  EXPECT_FALSE(tree->Find(5));
361  }
362 
363  // Basic construction - Elements should be found - not others
364  {
365  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
366  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
367  EXPECT_EQ(1, tree->Find(1)->GetData());
368  EXPECT_EQ(2, tree->Find(2)->GetData());
369  EXPECT_EQ(3, tree->Find(3)->GetData());
370  EXPECT_FALSE(tree->Find(0));
371  EXPECT_FALSE(tree->Find(5));
372  }
373 
374  // Basic construction on sorted array
375  {
376  const Container kSmallSorted(SmallIntArraySorted,
377  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
378  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
379  EXPECT_EQ(1, tree->Find(1)->GetData());
380  EXPECT_EQ(2, tree->Find(2)->GetData());
381  EXPECT_EQ(3, tree->Find(3)->GetData());
382  EXPECT_FALSE(tree->Find(0));
383  EXPECT_FALSE(tree->Find(5));
384  }
385 
386  // Basic construction with negative values and dupplicates - should be found
387  {
388  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
389  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
390  EXPECT_EQ(-18, tree->Find(-18)->GetData());
391  EXPECT_EQ(-5, tree->Find(-5)->GetData());
392  EXPECT_EQ(5, tree->Find(5)->GetData());
393  EXPECT_FALSE(tree->Find(1));
394  EXPECT_FALSE(tree->Find(6));
395  }
396 }
TEST ( TestBST  ,
Remove   
)

Definition at line 399 of file TestBinarySearchTree.cxx.

400 {
401  // Empty managed object - Should not change the status
402  {
403  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
404  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin());
405  ASSERT_TRUE(tree == nullptr);
406  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
407  EXPECT_TRUE(returnTreePtr == nullptr);
408  EXPECT_TRUE(tree == nullptr);
409  }
410 
411  // Unique element - Root should be erased
412  {
413  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
414  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
415  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
416  EXPECT_TRUE(returnTreePtr == nullptr);
417  EXPECT_TRUE(tree == nullptr);
418  }
419 
420  // Serie of same element - all nodes should be erased
421  {
422  const Container kSmallIntArray(5, 4);
423  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
424  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 4);
425  EXPECT_TRUE(returnTreePtr == nullptr);
426  EXPECT_TRUE(tree == nullptr);
427  }
428 
429  // Leaf node
430  {
431  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
432  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
433  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 3);
434 
435  ASSERT_TRUE(tree);
436  EXPECT_EQ(tree.get(), returnTreePtr);
437  EXPECT_EQ(2, tree->GetData());
438  ASSERT_TRUE(tree->GetLeftChild() != nullptr);
439  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
440  EXPECT_TRUE(tree->GetRightChild() == nullptr);
441  }
442 
443  // Root node with a unique child (left)
444  {
445  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
446  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 2);
447  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
448 
449  ASSERT_TRUE(tree);
450  EXPECT_EQ(tree.get(), returnTreePtr);
451  EXPECT_EQ(1, tree->GetData());
452  EXPECT_TRUE(tree->GetRightChild() == nullptr);
453  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
454  }
455 
456  // Root node with a unique child (right)
457  {
458  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
459  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin() + 1, kSmallIntArray.end());
460  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 1);
461 
462  ASSERT_TRUE(tree);
463  EXPECT_EQ(tree.get(), returnTreePtr);
464  EXPECT_EQ(3, tree->GetData());
465  EXPECT_TRUE(tree->GetRightChild() == nullptr);
466  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
467  }
468 
469  // Root node with a unique subtree child (left)
470  {
471  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
472  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
473  tree->Insert(0);
474  tree->Insert(-2);
475  tree->Insert(-1);
476  tree->Insert(-3);
477  tree->Insert(1);
478  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
479 
480  ASSERT_TRUE(tree);
481  EXPECT_EQ(tree.get(), returnTreePtr);
482  EXPECT_EQ(0, tree->GetData());
483  ASSERT_TRUE(tree->GetRightChild());
484  EXPECT_EQ(1, tree->GetRightChild()->GetData());
485  ASSERT_TRUE(tree->GetLeftChild());
486  EXPECT_EQ(-2, tree->GetLeftChild()->GetData());
487  EXPECT_EQ(3, tree->GetLeftChild()->Size());
488  }
489 
490  // Root node with a unique subtree child (right)
491  {
492  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
493  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
494  tree->Insert(4);
495  tree->Insert(6);
496  tree->Insert(5);
497  tree->Insert(7);
498  tree->Insert(3);
499  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
500 
501  ASSERT_TRUE(tree);
502  EXPECT_EQ(tree.get(), returnTreePtr);
503  EXPECT_EQ(4, tree->GetData());
504  ASSERT_TRUE(tree->GetLeftChild());
505  EXPECT_EQ(3, tree->GetLeftChild()->GetData());
506  ASSERT_TRUE(tree->GetRightChild());
507  EXPECT_EQ(6, tree->GetRightChild()->GetData());
508  EXPECT_EQ(3, tree->GetRightChild()->Size());
509  }
510 
511  // Root node with two childred
512  {
513  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
514  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
515  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
516 
517  ASSERT_TRUE(tree);
518  EXPECT_EQ(tree.get(), returnTreePtr);
519  EXPECT_EQ(1, tree->GetData());
520  ASSERT_TRUE(tree->GetRightChild());
521  EXPECT_EQ(3, tree->GetRightChild()->GetData());
522  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
523  }
524 
525  // Root node with two subtrees children
526  {
527  const Container kContainerValue(1, 10);
528  Const_Own_BST tree = Const_BST::Build(kContainerValue.begin(), kContainerValue.end());
529  tree->Insert(4);
530  tree->Insert(14);
531  tree->Insert(2);
532  tree->Insert(12);
533  tree->Insert(8);
534  tree->Insert(7);
535  tree->Insert(15);
536  tree->Insert(6);
537  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 10);
538 
539  ASSERT_TRUE(tree);
540  EXPECT_EQ(tree.get(), returnTreePtr);
541  EXPECT_EQ(8, tree->GetData());
542  EXPECT_EQ(8, tree->Size());
543  ASSERT_TRUE(tree->GetRightChild());
544  EXPECT_EQ(3, tree->GetRightChild()->Size());
545  ASSERT_TRUE(tree->GetLeftChild()->GetRightChild());
546  ASSERT_EQ(7, tree->GetLeftChild()->GetRightChild()->GetData());
547  }
548 }