C++ EASY TO SOLVE || Beginner Friendly with detailed explanations and dry run
Behold the legendary battle between Recursive and Interative Approaches \n\nFight!!!\n\nIntuition:-\n We are given a prefect binary tree that means every parent
> # **Behold the legendary battle between Recursive and Interative Approaches** \n***\n***Fight!!!***\n***\n**Intuition:-**\n* We are given a prefect binary tree that means every parent has two children and all the    leaves are on the same level . \n* This question is an superior version of binary level order traversal .\n* In level order traversal you will traverse each level of binary tree while outputting the data in that form . So the only difference is that somehow we need to connect the previous levels rightmost node to the next level\'s leftmost node and that\'s it .\n\n**Algorithm:-**\n1. Base case: if the root is null than return null\n2. Now to connect the left subtree of same level with right subtree of that level \n3. The only new line that differentiate from level order traversing is that we need to connect the rightmost node of a level to the leftmost node of the next level.\n4. Now just repeat the steps over and over for every level of tree . \n\n![image](https://assets.leetcode.com/users/images/6a41f9e5-3ba0-4116-ac09-f7e4a4bfdb19_1640748379.9406984.png) *Image credit goes to @Stargarth*\n\n**We can code this approach by two methods:**\n1. By recursive \n2. Iterative\n<mark>Both solution has time complexity and space complexity as O(n) and O(1) in a virtual manner but if we consider in a true sense than in recursion we use a recursive stack which has some space complexity .<mark>\nSo in a real sense the iterative solution is the best since it has truly O(1) space complexity .\n***\n**Recursive Approach Code:-**\n```\n//Upvote and Comment \n\nclass Solution {\npublic:\nNode* connect(Node* root) {\n    //base case\n    if(root == NULL) return NULL;\n    //connects the left subtree of same level with right subtree of that same level \n    if(root->left != NULL) root->left->next = root->right;\n    //connect the rightmost node of a level to the leftmost node of the next level.\n    if(root->right != NULL && root->next != NULL) root->right->next = root->next->left;\n    //recursive calls for left and right subtrees.\n    connect(root->left);\n    connect(root->right);\n    return root;\n   }\n};\n```\n***\n**Iterative Approach:-**\nIn iterative approach we will be needing two more pointers named as `curr` and `prev` for linking of left and right nodes\n```\n//Upvote and Comment\n\nclass Solution {\npublic:\n    Node* connect(Node* root) {\n        //Initialize pointers\n        Node *prev = root, *curr;\n        while (prev) {\n            curr = prev;\n            while (curr && curr->left) { \n                //connects the left subtree of same level with right subtree of that same level \n                curr->left->next = curr->right;\n                //connect the rightmost node of a level to the leftmost node of the next level.\n                if (curr -> next) curr->right->next = curr->next->left;\n                curr = curr->next;\n            }\n            prev = prev -> left;\n        }\n        return root;\n    }\n};\n```\n
['Recursion', 'C', 'Iterator', 'C++']