117. Populating Next Right Pointers in Each Node II

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii
• topics: Tree

Description

Given a binary tree

struct Node { int val; Node *left; Node *right; Node *next; }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow-up:

• You may only use constant extra space.
• The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Idea

Once we are done establishing the next pointers between the nodes, don’t they kind of represent a linked list? After the next connections are established, all the nodes on a particular level actually form a linked list via these next pointers. Based on this idea, we have the following intuition for our space efficient algorithm:

We only move on to the level N+1 when we are done establishing the next pointers for the level N. So, since we have access to all the nodes on a particular level via the next pointers, we can use these next pointers to establish the connections for the next level or the level containing their children.

Code

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
 
        dummy=Node(0)        
        head=root        
 
        while head:
            curr=head # initialize current level's head
            prev=dummy # init prev for next level linked list traversal
			# iterate through the linked-list of the current level and connect all the siblings in the next level
            while curr:  
                if curr.left:
                    prev.next=curr.left
                    prev=prev.next
                if curr.right:
                    prev.next=curr.right
                    prev=prev.next                                                
                curr=curr.next
            head=dummy.next # update head to the linked list of next level
            dummy.next=None # reset dummy node
        return root