Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

C++ unordered_map implementation problem previous values in map get forgotten

In the below code why map size is always 1, it is not saving previous values of root->val in the map as I can see in stdout. I was expecting that it should remember all the values put in the map.

/**
 * 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 FindElements {
public:

    unordered_map<int,int>mp;

    FindElements(TreeNode* root) {
        if(!root) return;
        if(root->val==-1){
            root->val=0;
        }
        mp[root->val]=1;
        
        // output
        cout<<root->val<<" "<<mp[root->val]<<" "<<mp.size()<<endl;
        
        if(root->left){
            root->left->val=2*(root->val)+1;
            FindElements(root->left);
        }
        if(root->right){
            root->right->val=2*(root->val)+2;
            FindElements(root->right);
        }
    }
    
    bool find(int target) {
        return mp[target];
    }
};
/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

enter image description here

Input:

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

["FindElements","find","find","find"]    
[[[-1,-1,-1,-1,-1]] , [1] , [3] , [5]]

Output:

[null,false,false,false]

Expected:

[null,true,true,false]

stdout:

0 1 1     
1 1 1     
3 1 1    
4 1 1    
2 1 1    

key,value,map-size

I was expecting that in each row map size values get increased.

leetcode problem link

>Solution :

Your code looks like you make an recursive call, to make a depth first search on the tree, but in fact it does not.

Because you are not using a normal member function, but the constructor, and a constructor can not be called recursive.

The syntax that look like recursion is instead the creation of additional temporary objects which will be destroyed after tge line ends.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading