ERROR: Abort signal from abort(3) (SIGABRT) on "Burning Tree" challenge

Question

I am looking at the Geeks for Geeks problem Burning Tree:

Given a binary tree and a node called target. Find the minimum time required to burn the complete binary tree if the target is set on fire. It is known that in 1 second all nodes connected to a given node get burned. That is its left child, right child, and parent.

I am getting the following error:

Abort signal from abort(3) (SIGABRT)

This is my code:

class Solution {
    // mapping to parent
    // returns the target node
    Node* createParentMapping(Node* root, int target,
                              map<Node*, Node*> &nodeToParent) {
        Node* res = NULL;
        queue<Node*> que;
        que.push(root);
        nodeToParent[root] = NULL;
        while (!que.empty()) {
            Node* front = que.front();
            if (front->data == target) {
                res = front;
            }
            if (front->left) {
                nodeToParent[front->left] = front;
                que.push(front->left);
            }
            if (front->right) {
                nodeToParent[front->right] = front;
                que.push(front->right);
            }
        }
        return res;
    }

    // burns the tree
    int burnTree(Node* root, map<Node*, Node*> &nodeToParent) {
        map<Node*, bool> visited;
        queue<Node*> q;
        q.push(root);
        visited[root] = true;
        int ans = 0;
        while (!q.empty()) {
            bool flag = 0;
            int size = q.size();
            for(int i = 0; i < size; i++) {
                Node* front = q.front();
                q.pop();
                if (front->left && !visited[front->left]) {
                    flag = 1;
                    q.push(front->left);
                    visited[front->left] = 1;
                }
                if (front->right && !visited[front->right]) {
                    flag = 1;
                    q.push(front->right);
                    visited[front->right] = 1;
                }
                if (nodeToParent[front] && !visited[nodeToParent[front]]) {
                    flag = 1;
                    q.push(nodeToParent[front]);
                    visited[nodeToParent[front]] = 1;
                }
            }
            if (flag == 1) {
                ans++;
            }
        }
        return ans;
    }
    
public:
    int minTime(Node* root, int target) {
        map<Node*, Node*> NodeToParent;
        Node* targetNode = createParentMapping(root, target, NodeToParent);
        int time = burnTree(targetNode, NodeToParent);
        return time;
    }
};

I am not able to find out the where the problem lies. What am I missing?

First of all create a proper [mre] that you can build and run locally. Hard-code the input that causes the crash. Then [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your program. For example by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to catch the crash and locate when and where in your code it happens, and examine variables and all the values. — Some programmer dude, Aug 07 '22 at 06:09
`SIGABRT` comes from `abort(3)`, as it says, which in turn can come from an assertion failure. You need to dig deeper than this. Try a debugger. And please format your code properly. — user207421, Aug 08 '22 at 09:47

trincot · Answer 1 · 2022-08-09T11:15:58.100

The problem is that you have an infinite loop in createParentMapping. A call to que.pop() is missing. Just like you did in burnTree, you should put it right after the line with que.front().

This will solve your problem.

But I should mention this problem can be solved without an extra data structure. Think of how path lengths relate to heights of (sub)trees.

Here is a spoiler solution that performs one recursive traversal of the tree:

class Solution { int answer; // Returns: // when negative: (negated) level at which target was found (= -(depth + 1)) // otherwise: number of levels in the tree (= height + 1) // Side effect: // adjusts answer int scanTree(Node* root, int target) { if (root == nullptr) return 0; // #levels int left = scanTree(root->left, target); int right = scanTree(root->right, target); if (root->data == target) { // found target. answer = max(left, right); // #levels => height return -1; // negative depth at which target was found } if (left < 0) { // Found the target in left subtree answer = max(answer, right - left); return left - 1; // Increased negative depth } else if (right < 0 ) { // Found the target in right subtree answer = max(answer, left - right); return right - 1; // Increased negative depth } else { // No success: return number of levels return 1 + max(left, right); } } public: int minTime(Node* root, int target) { answer = -1; scanTree(root, target); return answer; } };

ERROR: Abort signal from abort(3) (SIGABRT) on "Burning Tree" challenge

1 Answers1