Leetcode discuss: 116. Populating Next Right Pointers in Each Node

Here is the post.

C# tree level by level order traversal practice in June 2020

June 24, 2020

It is second algorithm in one of my mock interviews. I finished in less than 15 minutes.

Level by level order traversal

It is common practice to use Queue to enforce level by level order traversal, the order is maintained using FIFO, and also the size of level is easy to get by a query inside a while loop.

The another technique is to define a previous variable as Node object. Assign previous.next to current node in level order traversal.

public class Solution {
    public Node Connect(Node root) {
        if(root == null)
            return null; 
        
        // Run level by level order traversal
        // set a previous node in the same level
        var queue = new Queue<Node>(); 
        queue.Enqueue(root);
        
        while(queue.Count > 0)
        {
            var size = queue.Count; 
            
            Node previous = null; 
            for(int i = 0; i < size; i++)
            {
                var node = queue.Dequeue(); 
                if(node.left != null)
                    queue.Enqueue(node.left); 
                if(node.right != null)
                    queue.Enqueue(node.right);
                
                if(previous != null)
                    previous.next = node; 
                
                previous = node; 
            }
        }
        
        return root; 
    }
}