116. Populating Next Right Pointers in Each Node

using DFS

T: O(n)

S: O(n)

```java
/*
assume node1 is 2, node2 is 3
link node1.left and node1.right (4,5)
link node2.left and node2.right (6,7)

because  5, 6 also need to link, so we should...
link node1.right and node2.left
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        dfs(root.left, root.right);
        return root;
    }
    private void dfs(Node node1, Node node2) {
        if (node1 == null && node2 == null) {
            return;
        }
        node1.next = node2;
        dfs(node1.left, node1.right);
        dfs(node2.left, node2.right);
        dfs(node1.right, node2.left);
    }
}
```

using BFS

T: O(n)

S: O(n)

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};

*/

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int qSize = queue.size();
            Node prev = null;
            for (int q = 0; q < qSize; q++) {
                Node curr = queue.poll();
                if (prev != null) {
                    prev.next = curr;
                }
                prev = curr;

                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
        }
        return root;
    }
}


/**


BFS 
from last to link

prev = null
//
pop prev = curr

prev != null
prev.next = curr
prev = curr
 */




```