why this code has runtime error: shift exponent 32 is too large for 32-bit type 'int'?

留在故乡的纯情 0
Viewed 46

I am working on a code challenge where I need to find the number of nodes in a complete binary tree. The number of nodes is at most 50000.

When I submitted the code below, the evaluator reported an "int overflow error" on the statement ans += (1 << depth).

My question

Given the maximum number of nodes, I'd think the depth of the tree is at most 16, and the value of depth should not reach 32. So then why do I get an int overflow error?

My code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        queue<TreeNode*> que;
        int depth = 0;
        que.push(root);
        long ans = 0;
        while(!que.empty())
        {
            depth++;
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                if(!node->left)
                {
                    if(!i) ans += (1 << depth);
                    else ans += (1 << depth) + (1 << i);
                    break;
                }
                else que.push(node->left);
                if(!node->right)
                {
                    if(!i) ans += (1 << depth) + 1;
                 
                    else ans += (1 << depth) + (1 << i) + 1;
                    break;
                }
                else que.push(node->right);
                que.pop();
            }
        }
        return ans;
    }
};
binary-tree c++
1 Answers

The problem is that your algorithm gets into an infinite loop with an ever-increasing value for depth.

When one of the break statements is executed, the inner loop exits, and so there potentially remain some nodes on the queue that still belong to the same level. Then the outer loop makes its next iteration, only to process the same queue element again, leading to a break, ...etc, ...etc. The queue never becomes empty.

The solution is to not break, but return: there is no need to search any further. There is also no need to keep ans and add values to it. Once you get at a missing child, you just need the right formula (it was not entirely correct) and return it:

                if(!node->left)
                {
                    return (1 << depth) - 1 + (i << 1);
                }
                else que.push(node->left);
                if(!node->right)
                {
                    return (1 << depth) - 1 + (i << 1) + 1;
                }
                else que.push(node->right);

On a side note, this algorithm traverses the tree level by level. It will so visit half of the nodes before finding a node that does not have two children, and then it returns. This means this algorithm has a time complexity of O(), where is the number of nodes in the complete binary tree.

It is possible to do this with a time complexity of O(log²). So if that is the efficiency that is required, the above corrected solution might still be rejected with a timeout.

trincot0
Related