BFS solution || Explanation || Complexities
Intuition\nThe goal of this problem is to connect each node at the same level in a perfect binary tree to its immediate neighbor on the right. By establishing t
### Intuition\nThe goal of this problem is to connect each node at the same level in a perfect binary tree to its immediate neighbor on the right. By establishing these connections, each node\u2019s `next` pointer will point to the adjacent node on the same level, or to `None` if it\u2019s the last node in that level. A perfect binary tree allows us to do this efficiently by taking advantage of the tree\'s structure.\n\n### Approach\n1. **Iterate Level by Level**:\n   - Start with the root of the tree. Use the `leftmost` pointer to keep track of the leftmost node at each level.\n   - For each level, iterate through nodes using their `next` pointers (which have been set in the previous level) to avoid extra space.\n\n2. **Connect Nodes at Each Level**:\n   - For each node `current` at a level, connect its `left` child to its `right` child.\n   - If `current` has a `next` node, connect `current.right.next` to `current.next.left`. This connects nodes across subtrees.\n\n3. **Move to the Next Level**:\n   - After finishing connections for the current level, move `leftmost` down to `leftmost.left` (i.e., the start of the next level).\n\nThis method only uses pointers, without extra data structures like queues or lists, meeting the constant extra space requirement (apart from the implicit stack space if done recursively).\n\n### Complexity\n- **Time Complexity**: \\(O(n)\\), where \\(n\\) is the total number of nodes in the tree. Each node is visited once, and setting the `next` pointers takes constant time for each node.\n- **Space Complexity**: \\(O(1)\\) extra space, since we only use pointers to traverse the tree level by level. Implicit stack space is ignored as per the problem\'s constraints.\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    Node* connect(Node* root) {\n        if(root == NULL) return NULL;\n\n        Node* leftmost = root;\n\n        while(leftmost->left){\n            Node* cur = leftmost;\n\n            while(cur){\n                cur->left->next = cur->right;\n\n                if(cur->next){\n                    cur->right->next = cur->next->left;\n                }\n\n                cur = cur->next;\n            }\n\n            leftmost = leftmost->left;\n        }\n\n        return root;\n    }\n};\n```\n``` python []\nclass Solution:\n    def connect(self, root: \'Node\') -> \'Node\':\n        if root is None:\n            return None\n\n        leftmost = root\n\n        while leftmost.left:\n            cur = leftmost\n\n            while cur:\n                cur.left.next = cur.right\n\n                if cur.next:\n                    cur.right.next = cur.next.left\n\n                cur = cur.next\n\n            leftmost = leftmost.left\n\n        return root\n\n```
['Linked List', 'Tree', 'Breadth-First Search', 'Binary Tree', 'C++', 'Python3']