✅C++ || 2 Methods With Logic || BFS Traversal || CLEAN CODE
Method -1 [Naive Method]\n\n\n\nn==Number of Nodes \nT->O(n) && S->O(n) [For storing all the Nodes after BFS] + O(n/2) [For queue, worst Case as it\'s a Perfect
***Method -1 [Naive Method]***\n\n![image](https://assets.leetcode.com/users/images/c1e0a6f5-6652-42c9-be2d-d4dd6b797b16_1672731185.2271147.png)\n\n**n==Number of Nodes \nT->O(n) && S->O(n) [For storing all the Nodes after BFS] + O(n/2) [For queue, worst Case as it\'s a Perfect Binary Tree]**\n\n***Logic -> Level Order Traversal and connect adjacent Nodes!***\n\n\tclass Solution {\n\t\tpublic:\n\t\t\tNode* connect(Node* root) {\n\t\t\t\tif(!root) return NULL;\n\n\t\t\t\tvector<vector<Node*>> lvl;\n\t\t\t\tqueue <Node*> q;\n\t\t\t\tq.push(root);\n\n\t\t\t\twhile(!q.empty()){\n\t\t\t\t\tint size = q.size();\n\t\t\t\t\tvector <Node*> temp;\n\n\t\t\t\t\tfor(int i = 0 ; i < size ; i++){\n\t\t\t\t\t\tNode* node = q.front();\n\t\t\t\t\t\tq.pop();\n\t\t\t\t\t\tif(node -> left) q.push(node -> left);\n\t\t\t\t\t\tif(node -> right) q.push(node -> right);\n\t\t\t\t\t\ttemp.push_back(node);\n\t\t\t\t\t}\n\n\t\t\t\t\ttemp.push_back(NULL);\n\t\t\t\t\tlvl.push_back(temp);\n\t\t\t\t} \n\n\t\t\t\tfor(int i = 0 ; i < lvl.size() ; i++){\n\t\t\t\t\tfor(int j = 0 ; j < lvl[i].size() - 1 ; j++) lvl[i][j] -> next = lvl[i][j + 1];\n\t\t\t\t}\n\n\t\t\t\treturn root;\n\t\t\t}\n\t\t};\n\t\t\n**Method - 2 [Optimized]**\n\n![image](https://assets.leetcode.com/users/images/2bedfde0-1ab4-4a19-b754-0fb7656b6c84_1672755793.910553.png)\n\n**n==Number of Nodes\nT->O(n) && S->O(n) [Recursive Stack Space]**\n\n\tclass Solution {\n\tpublic:\n\t\tvoid dfs(Node* l,Node* r){\n\t\t\tif(!l && !r) return;\n\n\t\t\tl -> next = r;\n\t\t\tr -> next = NULL;\n\n\t\t\tdfs(l -> left , l -> right);\n\t\t\tdfs(l -> right , r -> left);\n\t\t\tdfs(r -> left , r -> right);\n\t\t}\n\n\t\tNode* connect(Node* root) {\n\t\t\tif(!root) return NULL;\n\t\t\tdfs(root -> left , root -> right);\n\t\t\treturn root;\n\t\t}\n\t};
['Breadth-First Search', 'C', 'C++']