116. Populating Next Right Pointers in Each Node

class Solution {
    public Node connect(Node root) {
        // space (1) solution, BFS
        Node leftMost =root;
        while(leftMost !=null){
            Node curr = leftMost;
            // when there is node on the right of curr, and
            // curr has children
            while(curr!=null && curr.left!=null){
                curr.left.next = curr.right;
                curr.right.next = curr.next == null ? null : curr.next.left;
                curr = curr.next;
            }
            leftMost = leftMost.left;
        }
        return root;
    }
}

class Solution {
    public Node connect(Node root) {
        // use BFS
        // if use queue, the last level contains N/2N/2 nodes. space O(N)
        Node node = root;
        Queue<Node> queue = new LinkedList<>();
        if(root==null) return root;
        queue.offer(node);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                // poll and asign the first node in queue to current node
                node = queue.poll();
                if(i!=size-1) node.next= queue.peek();
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
        }
        return root;
    }
}