• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
Node* connect(Node* root) {
if (!root)
return nullptr;
connectTwoNodes(root->left, root->right);
return root;
}

private:
void connectTwoNodes(Node* p, Node* q) {
if (!p)
return;
p->next = q;
connectTwoNodes(p->left, p->right);
connectTwoNodes(q->left, q->right);
connectTwoNodes(p->right, q->left);
}
};
``````

## JAVA

``````class Solution {
public Node connect(Node root) {
if (root == null)
return null;
connectTwoNodes(root.left, root.right);
return root;
}

private void connectTwoNodes(Node p, Node q) {
if (p == null)
return;
p.next = q;
connectTwoNodes(p.left, p.right);
connectTwoNodes(q.left, q.right);
connectTwoNodes(p.right, q.left);
}
}
``````

## Python

``````class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None

def connectTwoNodes(p, q) -> None:
if not p:
return
p.next = q
connectTwoNodes(p.left, p.right)
connectTwoNodes(q.left, q.right)
connectTwoNodes(p.right, q.left)

connectTwoNodes(root.left, root.right)
return root
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
Node* connect(Node* root) {
Node* node = root;  // the node just above current needling

while (node && node->left) {
Node dummy(0);  // dummy node before needling
// needle children of node
for (Node* needle = &dummy; node; node = node->next) {
needle->next = node->left;
needle = needle->next;
needle->next = node->right;
needle = needle->next;
}
node = dummy.next;  // move node to the next level
}

return root;
}
};
``````

## JAVA

``````class Solution {
public Node connect(Node root) {
Node node = root; // the node just above current needling

while (node != null && node.left != null) {
Node dummy = new Node(); // dummy node before needling
// needle children of node
for (Node needle = dummy; node != null; node = node.next) {
needle.next = node.left;
needle = needle.next;
needle.next = node.right;
needle = needle.next;
}
node = dummy.next; // move node to the next level
}

return root;
}
}
``````

## Python

``````class Solution:
def connect(self, root: 'Node') -> 'Node':
node = root  # the node just above current needling

while node and node.left:
dummy = Node(0)  # dummy node before needling
# needle children of node
needle = dummy
while node:
needle.next = node.left
needle = needle.next
needle.next = node.right
needle = needle.next
node = node.next
node = dummy.next  # move node to the next level

return root
``````