algoadvance

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree is defined as follows:

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

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.

You need to write code that connects each node to its next right node.

Example

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like the diagram in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Clarifying Questions

  1. Input Description: Are we supposed to assume the input is given as a list representation of a perfect binary tree?
    • No, you can assume the input is given as a tree of connected Node objects.
  2. Node Class: Can I assume the Node class structure cannot be changed?
    • Yes, the Node class structure cannot be changed.
  3. Tree Properties: Can we assume that the tree is always a perfect binary tree?
    • Yes, you can assume the tree is always a perfect binary tree where all leaves are at the same level and every parent has two children.

Strategy

  1. Level Order Traversal:
    • We will use a level order traversal to connect nodes at the same level.
    • This can be done using a queue where for each level we connect nodes using their next pointers.
  2. Using a Linked List Approach:
    • Since it’s a perfect binary tree, we can use existing next pointers to traverse through each level.
    • Connect the children of nodes using their parent’s next pointers.

Code

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

def connect(root: 'Node') -> 'Node':
    if not root:
        return root

    # Start with the root
    leftmost = root

    # Traverse levels
    while leftmost.left:
        # Go through the current level
        head = leftmost
        while head:
            # Connect the children of the current node
            head.left.next = head.right
            # Connect right child to the next node's left child
            if head.next:
                head.right.next = head.next.left
            # Move to the next node
            head = head.next
        # Move to the next level
        leftmost = leftmost.left

    return root

# Example Usage
# root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
# connect(root)

Time Complexity

The time complexity for this algorithm is O(N) where N is the number of nodes in the tree. Each node is traversed exactly once, and the connections are made in constant time.

The space complexity is O(1) because we use no additional data structures that scale with input size, only a few pointers.

This solution efficiently connects all the nodes using their next pointers as required.

Try our interview co-pilot at AlgoAdvance.com