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

Number: 116

Difficulty: Medium

Paid? No

Companies: Meta, Bloomberg, Amazon, Google, Microsoft, Salesforce, Oracle, Snowflake, Walmart Labs, Apple, Flipkart, Citadel

Problem Description

Given a perfect binary tree where every node has exactly two children (except the leaves) and all leaves are on the same level, populate each node's "next" pointer so that it points to its next right node. If there is no right node, the "next" pointer should be set to null. Initially, all "next" pointers are null.

Key Insights

  • The tree is perfect, meaning that if a node exists, both its left and right children exist (except at the leaf level).
  • At each node, we can set:
    • node.left.next to node.right.
    • node.right.next to node.next.left (if node.next exists).
  • We can use a level-order traversal without extra space by linking nodes from left to right on the same level.
  • The approach only uses constant extra space (excluding recursion stack if used).

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(1) extra space (ignoring recursion stack or pointers used to traverse levels).

Solution

We can solve this problem by taking advantage of the perfect tree property. Starting from the root, we traverse each level using the already established "next" pointers. For each node at a given level, set the left child's "next" pointer to the right child. For the right child, if the node has a "next" pointer, link it to the left child of the node's next neighbor. After processing a level, move to the leftmost node of the next level. This iterative process continues until we reach a level without children.

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        # Node's value
        self.left = left      # Left child
        self.right = right    # Right child
        self.next = next      # Next right pointer

def connect(root: 'Node') -> 'Node':
    if not root:
        return root  # If tree is empty, return null

    # Start with the root node
    level_start = root
    while level_start.left:
        # Traverse nodes at the current level
        current = level_start
        while current:
            # Connect left child to right child
            current.left.next = current.right
            # Connect right child to the next node's left child if available
            if current.next:
                current.right.next = current.next.left
            # Move to the next node on the same level using next pointer
            current = current.next
        # Move to the leftmost node of the next level
        level_start = level_start.left

    return root  # Return the modified tree
← Back to All Questions