Problem: https://www.educative.io/m/connect-all-siblings

I'm attempting to connect all sibling nodes by creating a dummy node and set it's next to the node that we're currently visiting by using a next pointer, but after executing the code:

    public static void populate_sibling_pointers(BinaryTreeNode root) {
        if(root == null) return;
        Queue<BinaryTreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            int size = q.size();
            BinaryTreeNode dummy = new BinaryTreeNode(0);
            for(int i = 0; i < size; i  ){
                BinaryTreeNode cur = q.poll();
                dummy.next = cur;
                dummy = dummy.next;
                if(cur.left!=null){
                    q.offer(cur.left);
                }
                if(cur.right!=null){
                    q.offer(cur.right);
                }            
            }
        }
    }

I still failed to pass some test but I'm not sure what I did wrong here. Any help is appreciated!

CodePudding user response：

Two issues:

• You should create a new dummy node only once. By creating a new one at every iteration of the while loop, you break the chain of next references. So the creation of that node should happen before the while loop.

• The last node in the next chain should have its next set to null.

Here is the corrected code:

class connectSiblings{
    public static void populate_sibling_pointers(BinaryTreeNode root) {
        if(root == null) return;
        Queue<BinaryTreeNode> q = new LinkedList<>();
        q.offer(root);

        BinaryTreeNode dummy = new BinaryTreeNode(0);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i  ){
                BinaryTreeNode cur = q.poll();
                dummy.next = cur;
                dummy = dummy.next;
                if(cur.left!=null){
                    q.offer(cur.left);
                }
                if(cur.right!=null){
                    q.offer(cur.right);
                }            
            }
        }
        dummy.next = null;
    }
} 

You can further optimise this code by replacing the use of the LinkedList with the actual linked list you are building with the next references: when a layer of the tree has been correctly wired with next references, you can iterate that section of that linked list to find and wire the nodes of the next layer, which then can serve as linked list for the next layer, ...etc.