Level order traversal + CycleSort
please upvote if you like it \n\nLet us divide this problem into two different halfs \n\n1. Travel levels in order\n2. sort a level using minimum number of swap
<b>please upvote if you like it </b>\n\nLet us divide this problem into two different halfs \n\n1. Travel levels in order\n2. sort a level using minimum number of swaps\n\nTypically task 1 is what we call BFS or level order on tree\n\ntask2 is cycle sort\n\nNote :- Reposting this :( old one removed because I add learning resource to Cycle Sort\n\nFrom the question it is quite easy to understand that we will have to do a BFS more specifically on trees so we call it \n`Level order Traversal`\n\nOrdinary Level order traversal is not going to be of any help rather <i> we need a traversal where we can distinguish between each \nlevel</i> so we insert a `nullptr` into queue to mark the <b> end of level </b>\n\nCycle sort is used to solve problems where we need minimum swaps or to find missing numbers in a given range problem .\n\n\n#### Solution point :- \n\nSo after every level we have a nullptr thus if we can get to sort the numbers at each level in minimum number of swaps i.e all we need .\n\nAnd one such sort that does minimum swaps or memory writes is <b>`Cycle Sort` </b> it selects a element and then solves its cyle .  \n<hr>\n\n\n\nfor more cycle sort problems visit this post [Post](https://leetcode.com/discuss/study-guide/1902662/cyclic-sort-very-important-and-less-known-pattern)\n<hr>\n\n#### Code :-\n```c++\nclass Solution {\npublic:\n    int cycleSort(vector<int>& nums)\n    {\n      int n = nums.size();\n        int len = n;\n        map<int, int> map;\n        for (int i = 0; i < len; i++)\n            map[nums[i]] = i;\n        sort(nums.begin(), nums.end());\n        bool visited[len];\n        for(int i = 0; i < len ; i++) visited[i] = false;\n        int ans = 0;\n        for (int i = 0; i < len; i++)\n        {\n\t\t // already swapped and corrected or already present at correct pos\n            if (visited[i] || map[nums[i]] == i)\n                continue;\n            int j = i, cycle_size = 0;\n            while (!visited[j])\n            {\n                visited[j] = true;\n\t\t\t\t// move to next node\n                j = map[nums[j]];\n                cycle_size++;\n            }\n            if (cycle_size > 0)\n            {\n\t\t\t// Update answer by adding current cycle.\n                ans += (cycle_size - 1);\n            }\n        }\n        return ans;\n    }\n\n    int minimumOperations(TreeNode* root) {\n        queue<TreeNode*> q;\n        q.push(root);\n\t\t// nullptr to identify end of level\n        q.push(nullptr);\n        vector<int> v;\n        int ans = 0;\n        while(!q.empty()){\n            auto temp = q.front();\n            q.pop();\n            if(!temp){\n                ans += cycleSort(v);\n\t\t\t\t// clear values of old level\n                v.clear();\n\t\t\t\t// if there are more elements in queue then push null to identify end else no elements are present \n\t\t\t\t// so don\'t push anything\n                if(!q.empty())\n                    q.push(nullptr);\n            }else{\n                v.push_back(temp->val);\n                if(temp->left) q.push(temp->left);\n                if(temp->right) q.push(temp->right);\n            }\n\n        }\n        \n        return ans;\n    }\n};\n```\n\n`Time Complexity : O(nlogn)`\n`Space Complexity: O(n)`\n\nFollow up to this problem would be :- \n\nWhat if adjacnecy matrix is given and when we swap the nodes its subtree also gets swapped \n\n(I was asked this question in Fanatics company interview 18CTC)\n\n
[]