Connect Next Right Pointers in Tree

# Connect Next Right Pointers in Tree ## Difficulty Medium ## Tags `tree`, `bfs` ## Problem Statement You are given a **perfect binary tree** where all leaves are on the same level and every parent has two children. Each node has a `next` pointer initially set to `None`. Populate each `next` pointer to point to its next right node. If there is no next right node, set it to `None`. ## Constraints - The tree is a perfect binary tree. - Number of nodes is in range [0, 2¹² - 1]. - Try to use O(1) extra space (recursion stack doesn't count). ## Signatures ### Python ```python def connect(root: TreeNode) -> TreeNode: pass ``` ### Java ```java public class Solution { public TreeNode connect(TreeNode root) { return null; } } ``` ### Csharp ```csharp public class Solution { public TreeNode connect(TreeNode root) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: TreeNode* connect(TreeNode* root) { } }; ``` ### C ```c TreeNode* connect(TreeNode* root) { } ``` ### Ruby ```ruby def connect(root) end ``` ### Perl ```perl sub connect { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def connect(root: TreeNode): TreeNode = { } } ``` ### Haskell ```haskell connect :: ... -> ... connect args = undefined ``` ### Clojure ```clojure (defn connect [root] ) ``` ### Scheme ```scheme (define (connect root) ) ``` ## Examples ### Example 1 **Input:** ``` 1 / \ 2 3 / \ / \ 4 5 6 7 ``` **Output:** ``` 1 → None / \ 2 → 3 → None / \ / \ 4→5→6→7 → None ``` **Explanation:** Each node points to its right neighbor at the same level. ### Example 2 **Input:** ``` root = [] ``` **Output:** ``` [] ``` ## Hints 1. **BFS with Queue** (O(N) space): Process level by level, link nodes. 2. **O(1) Space**: Use already-established next pointers to traverse. - `node.left.next = node.right` - `node.right.next = node.next.left` (if node.next exists) 3. Process level by level using leftmost node of each level.