# 117. Populating Next Right Pointers in Each Node II

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: Node* connect(Node* root) { Node* node = root; // The node just above current needling while (node) { Node dummy(0); // Dummy node before needling // Needle children of node for (Node* needle = &dummy; node; node = node->next) { if (node->left) { // Needle left child needle->next = node->left; needle = needle->next; } if (node->right) { // Needle right child needle->next = node->right; needle = needle->next; } } node = dummy.next; // Move node to the next level } return root; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public Node connect(Node root) { Node node = root; // The node just above current needling while (node != null) { Node dummy = new Node(); // Dummy node before needling // Needle children of node for (Node needle = dummy; node != null; node = node.next) { if (node.left != null) { // Needle left child needle.next = node.left; needle = needle.next; } if (node.right != null) { // Needle right child needle.next = node.right; needle = needle.next; } } node = dummy.next; // Move node to the next level } return root; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def connect(self, root: 'Node') -> 'Node': node = root # The node just above current needling while node: dummy = Node(0) # Dummy node before needling # Needle children of node needle = dummy while node: if node.left: # Needle left child needle.next = node.left needle = needle.next if node.right: # Needle right child needle.next = node.right needle = needle.next node = node.next node = dummy.next # Move node to the next level return root