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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Populating Next Right Pointers in Each Node II

Difficulty: Medium

Problem Description

Given a binary tree, 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.

Key Insights

  • The tree is a binary tree where each node has a next pointer.
  • The task requires connecting nodes at the same level.
  • A breadth-first search (BFS) approach can be utilized to traverse the tree level by level.
  • We can maintain a queue to facilitate level order traversal.
  • The solution should operate with constant extra space, implying we can use the next pointers themselves for traversal.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as each node is visited once. Space Complexity: O(1) - since we are only using the next pointers and not additional data structures for storing nodes.

Solution

To solve the problem, we will use a breadth-first search (BFS) approach. We traverse the tree level by level, using a pointer to track the current node and link its next pointer to the next node on the same level. This allows us to connect all nodes at the same level without using any additional data structures apart from the existing next pointers.

Code Solutions

class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

def connect(root: Node) -> Node:
    if not root:
        return None
    
    # Start with the leftmost node of the tree
    leftmost = root
    
    while leftmost:
        # Traverse nodes at the current level
        current = leftmost
        prev = None
        leftmost = None
        
        while current:
            # Process the left child
            if current.left:
                if not leftmost:
                    leftmost = current.left
                if prev:
                    prev.next = current.left
                prev = current.left
            
            # Process the right child
            if current.right:
                if not leftmost:
                    leftmost = current.right
                if prev:
                    prev.next = current.right
                prev = current.right
            
            current = current.next
            
    return root
← Back to All Questions