Finding circular reference in a binary tree | Together C & C++ | Page 1

warm marten Apr 3, 2025, 8:35 PM

#

I am attempting to write a program that will find a circular reference (reference to a parent or ancestor) within a binary tree that has no clear sorting order.

The Node class constructor is as follows:

   int key;
   Node* left;
   Node* right;

   Node(int nodeKey, Node* leftChild = nullptr, Node* rightChild = nullptr) {
      key = nodeKey;
      left = leftChild;
      right = rightChild;
   }

The section of the client program that my solution fails on is as follows:



   Node* rootRight = new Node(89);
   root = new Node(87, new Node(51), rootRight);
   badNode = new Node(91, rootRight, nullptr);
   rootRight->right = badNode;

   // Call the user's CheckBSTValidity() function
   userResult = BSTChecker::CheckBSTValidity(root);

   // Check the user's result
   if (badNode == userResult) {
      cout << "CheckBSTValidity() correctly returned the rule-violating node." << endl;
   }
   else if (nullptr == userResult) {
      cout << "CheckBSTValidity() returned nullptr for an invalid tree." << endl;
   }
   else {
      cout << "CheckBSTValidity() returned a node that is not the BST ";
      cout << "rule-violating node." << endl;
   }

   // Remove the circular reference, then delete the tree
   rootRight->right = nullptr;
   Node::DeleteTree(root);








   // Create the invalid tree wherein a node has a child that references an
   // ancestor. The ancestor is NOT the immediate parent, nor the root.
   root = new Node(51, new Node(27, new Node(14), nullptr), nullptr);
   badNode = new Node(92);
   Node* node83 = new Node(83, new Node(77), badNode);
   Node* node72 = new Node(72, nullptr, node83);
   badNode->left = node72;
   root->right = node72;

   // Call the user's CheckBSTValidity() function
   userResult = BSTChecker::CheckBSTValidity(root);

   // Check the user's result
   if (badNode == userResult) {
      cout << "CheckBSTValidity() correctly returned the rule-violating node." << endl;
   }
   else if (nullptr == userResult) {
      cout << "CheckBSTValidity() returned nullptr for an invalid tree." << endl;
   }
   else {
      cout << "CheckBSTValidity() returned a node that is not the BST ";
      cout << "rule-violating node." << endl;
   }

And my program to check if a specific node violates the condition is as follows:


    static bool CheckIsDescendant(Node* root, Node* descendant){




        if (root == nullptr){
            return false;
        }


        if (root == descendant){
            return true;
        }



        return CheckIsDescendant(root->left, descendant) || CheckIsDescendant(root->right, descendant);

    }


    static Node* CheckChildrenAreParents(Node* node){
        if (node == nullptr){
            return nullptr;
        }



        Node* left = CheckChildrenAreParents(node->left);


        if (left != nullptr){
            return left;
        }



        if ((node->left && CheckIsDescendant(node->left, node)) || (node->right && CheckIsDescendant(node->right, node))){
            return node;
        }




        Node* right = CheckChildrenAreParents(node->right);



        if (right != nullptr){
            return right;
        }



        return nullptr;

    }

The program is segfaulting

stable jayBOT Apr 3, 2025, 8:35 PM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

opaque vortex Apr 3, 2025, 9:32 PM

#

warm marten I am attempting to write a program that will find a circular reference (referenc...

Have you used address sanitizer?

#

!asan

stable jayBOT Apr 3, 2025, 9:32 PM

#

opaque vortex !asan

Address Sanitizer

Memory errors in C and C++ are easy to make and they can be very hard to debug because they can manifest far from their source. Address sanitizer is a runtime checker that identifies memory errors at their source and makes debugging much simpler. Address sanitizer is available for gcc/clang on linux and msvc on windows. To use it simply pass -fsanitize=address to the compiler.

Note: Make sure to turn on debug symbols with -g for gcc/clang and -Zi for msvc.

Example

How to read sanitizer output

The first few lines tell you the problem, heap-use-after-free, due to performing a READ of size 4, at example.c line 7 (from the first line of the stack trace).

==1==ERROR: AddressSanitizer: heap-use-after-free on address ....
READ of size 4 at 0x602000000010 thread T0
    #0 0x40120f in main /app/example.c:7
    #1 0x7fda58629d8f  (...)
    #2 0x7fda58629e3f in __libc_start_main (...)
    #3 0x4010b4 in _start (...)

Additional information is also included such as where the allocation was performed and where the allocation was freed.

#Finding circular reference in a binary tree