*LC-117 Populating Next Right Pointers in Each Node II

        1
       /  \
      2    3
     / \    \
    4   5    7

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */

//version 1
// classical BFS solution (using Queue)
public class Solution {
    public void connect(TreeLinkNode root) {
         if(root==null) {
             return;
         }
         Queue queue = new LinkedList<>();
         queue.add(root);
         while(!queue.isEmpty()){
             int size = queue.size();
             for(int i=0; i

// version 1.2
// classical BFS solution (using two Queue for reference)
public class Solution {
    public void connect(TreeLinkNode root) {
        if( root == null) {
            return;
        }
           
        Queue queue = new LinkedList(); 
        queue.offer(root);
        while (!queue.isEmpty()){
            Queue next = new LinkedList();
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                 TreeLinkNode topNode = queue.poll();
                 //add pointer if next node in same level exist
                 if(queue.peek() != null) {
                      topNode.next = queue.peek();
                  }else {
                      topNode.next = null;
                  }
                  //add children to next level
                  if(topNode.left != null) {
                      next.offer(topNode.left);
                  }
                  if(topNode.right != null) {
                      next.offer(topNode.right);
                  }
            }
            queue = next;
        }
    }
}

//version 2
//hashmap solution 
public class Solution {
    public void connect(TreeLinkNode root) {
        HashMap map = new HashMap();
        traverse(root, map , 0);
    }
    private void traverse(TreeLinkNode root, HashMap map, int level){
        if(root == null) {
            return;
        }
        
        if (!map.containsKey(level)){
            map.put(level,root);
        } else {
            map.get(level).next = root;
            map.put(level, root);
        }
        level++;
        traverse(root.left, map, level);
        traverse(root.right, map, level);
    }
}