Using BFS and sentinel pointers


  • 0
    T

    Not using any additional space for the queue, since I am rearranging the input into a queue. Will work for complete and incomplete Binary Tree

    /**
     * Definition for binary tree with next pointer.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void connect(TreeLinkNode root) {
            if(root == null){
                return;
            }
            Queue<TreeLinkNode> q = new LinkedList();
            //Insert null to designate beginning of a new level
            q.offer(null);
            q.offer(root);
            TreeLinkNode prev = root;
            while(!q.isEmpty()){
                TreeLinkNode curr = q.poll();
                if(curr == null){
                    //Found a new level is available in the queue. Next few nodes in the queue will be of the current level. Nodes that will be added after these current elements in the queue are exhausted, will be be in the following level. Hence, add a null to designate this fact
                    if(!q.isEmpty()){
                        q.offer(null);
                    }
                    prev = null;
                    continue;
                }
                if(prev != null){
                    prev.next = curr;
                }
                prev = curr;
                if(curr.left != null){
                    q.offer(curr.left);
                }
                if(curr.right != null){
                    q.offer(curr.right);
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.