1
class Solution {
2
 public:
3
  // constant space
4
  // we only need start node of each level if we have already populated the next
5
  // right pointers in that level
6
  // node->left->next = node->right
7
  // if node->next != NULL , node->right->next = node->next=>left
8

9
  Node *connect(Node *root) {
10
    Node *temp = root;
11
    while (temp != NULL) {
12
      Node *start = temp;
13
      temp = start->left;
14
      if (temp != NULL) {
15
        while (start != NULL) {
16
          start->left->next = start->right;
17
          if (start->next != NULL) {
18
            start->right->next = start->next->left;
19
          }
20
          start = start->next;
21
        }
22
      }
23
    }
24
    return root;
25
  }
26
};