We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Populating Next Right Pointers in Each Node II

Number: 117

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Microsoft, Bloomberg, Google, Snowflake, Citadel, Walmart Labs

Problem Description

Given a binary tree, where each node contains an extra pointer called next, populate each next pointer to point to its next right node. If there is no next right node at any level, the pointer should be set to NULL. Initially, all next pointers are set to NULL.

Key Insights

  • The tree is not necessarily a perfect binary tree.
  • The problem requires an algorithm using constant extra space.
  • A level order traversal using established next pointers allows linking nodes on the next level without additional data structures.
  • Use pointers to keep track of the current level, the head of the next level, and the tail to build the next connections.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, because every node is processed once.
Space Complexity: O(1) extra space (ignoring the recursion stack if a recursive approach were used) by leveraging the next pointers for level order traversal.

Solution

The solution uses a level order traversal without using an explicit queue. Instead, it uses three pointers:

  1. current: iterates over nodes in the current level.
  2. nextHead: points to the first node in the next level.
  3. nextTail: used to connect nodes in the next level. For each node in the current level, if it has a left child, attach it to nextTail. Similarly, if it has a right child, attach it to nextTail. After processing the entire level, move to nextHead and continue the process. This guarantees constant extra space usage while linking all nodes appropriately.

Code Solutions

# Definition for a Node.
# class Node:
#     def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        # Start with the root node
        current = root
        # Process level by level until no nodes remain
        while current:
            # Initialize pointers for the next level
            nextHead = None
            nextTail = None
            # Traverse nodes in the current level using next pointers
            while current:
                # Process current node's left child
                if current.left:
                    if not nextHead:
                        nextHead = current.left
                        nextTail = current.left
                    else:
                        nextTail.next = current.left
                        nextTail = nextTail.next
                # Process current node's right child
                if current.right:
                    if not nextHead:
                        nextHead = current.right
                        nextTail = current.right
                    else:
                        nextTail.next = current.right
                        nextTail = nextTail.next
                # Move to the next node in current level
                current = current.next
            # Move to next level
            current = nextHead
        return root
← Back to All Questions