test: ensure rb node parents are equal

2 files changed, 23 insertions, 0 deletions

diff --git a/src/03/rb_tree.c b/src/03/rb_tree.c
index d1861f5..802791e 100644
--- a/src/03/rb_tree.c
+++ b/src/03/rb_tree.c
@@ -231,6 +231,15 @@ bool rb_equals(RBTree *tree, RBTree *other_tree) {
   if (!tree || !other_tree)
     return tree == other_tree;
 
+  if (tree->parent && !other_tree->parent)
+    return false;
+
+  if (!tree->parent && other_tree->parent)
+    return false;
+
+  if (tree->parent && tree->parent->value != other_tree->parent->value)
+    return false;
+
   return tree->value == other_tree->value
     && tree->colour == other_tree->colour
     && rb_equals(tree->left, other_tree->left)
diff --git a/src/03/rb_tree_test.c b/src/03/rb_tree_test.c
index 1bf4e5a..3fca748 100644
--- a/src/03/rb_tree_test.c
+++ b/src/03/rb_tree_test.c
@@ -226,6 +226,19 @@ Ensure(equals_returns_false_when_root_and_right_subtree_are_not_equal) {
   assert_that(rb_equals(tree, other_tree), is_equal_to(false));
 }
 
+Ensure(equals_returns_false_when_parent_is_not_equal) {
+  RBTree *tree = rb_tree_initialize(20);
+  tree = rb_tree_insert(tree, 30);
+
+  RBTree *other_tree = rb_tree_initialize(20);
+  other_tree = rb_tree_insert(other_tree, 30);
+
+  other_tree->right->parent = NULL;
+
+  assert_that(rb_equals(tree, other_tree), is_equal_to(false));
+  assert_that(rb_equals(other_tree, tree), is_equal_to(false));
+}
+
 Ensure(is_valid_returns_false_when_root_is_red) {
   RBTree *tree = rb_tree_initialize(20);
   tree->colour = red;
@@ -286,6 +299,7 @@ TestSuite *rb_tree_tests() {
   add_test(x, equals_returns_true_when_root_and_left_subtree_are_equal);
   add_test(x, equals_returns_false_when_root_and_left_subtree_are_not_equal);
   add_test(x, equals_returns_false_when_root_and_right_subtree_are_not_equal);
+  add_test(x, equals_returns_false_when_parent_is_not_equal);
 
   add_test(x, is_valid_returns_false_when_root_is_red);
   add_test(x, is_valid_returns_false_when_red_node_has_red_child);