NUHMAN.com

Introduction

LeetCode 116: Populating Next Right Pointers in Each Node asks us to populate each node’s next pointer in a perfect binary tree. Each node’s next pointer should point to its immediate neighbor to the right. If there is no next right node, the next pointer should be set to null.

This problem provides a perfect binary tree, meaning every parent node has either two children, or it’s a leaf node. The task is to fill the next pointer of each node.

Problem Statement

Given a perfect binary tree, populate each node’s next pointer to point to its next right node. If there is no next right node, the next pointer should be set to null.

Example:

go

Input: root = [1,2,3,4,5,6,7]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null]

Approach:

BFS Solution:

We can approach this problem using a breadth-first search (BFS) method. The key observation is that in a perfect binary tree, all nodes at the same level are connected, so we can traverse the tree level by level, populating each node's next pointer.

1. BFS Algorithm:

• Start by traversing the tree level by level.
• For each level, connect each node's next pointer to the next node in the same level.
• Use a queue to handle the nodes at each level.

1. Optimized Approach (O(1) space):

• Instead of using a queue, we can use the fact that each node's left child’s next pointer is already linked to its right child, and the right child's next pointer is already linked to its neighbor’s left child.
• Use two pointers: One to traverse the current level, and another to connect the next level nodes.

Go Implementation

Solution Using BFS with Queue

go

package main

// TreeNode represents a node in the binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
    Next  *TreeNode
}

// connect populates the next right pointers of each node.
func connect(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    // Initialize the current level starting with the root node
    currentLevelHead := root

    // Traverse the tree level by level
    for currentLevelHead != nil {
        // Traverse the current level
        current := currentLevelHead
        for current != nil {
            if current.Left != nil {
                current.Left.Next = current.Right // Connect the left child to the right child
            }
            if current.Right != nil && current.Next != nil {
                current.Right.Next = current.Next.Left // Connect the right child to the next left child
            }
            current = current.Next // Move to the next node in the current level
        }
        // Move to the next level (the leftmost node of the next level)
        currentLevelHead = currentLevelHead.Left
    }

    return root
}

Explanation:

1. TreeNode Structure:

• The TreeNode struct represents a node in the binary tree with an integer value (Val), pointers to the left and right children (Left, Right), and a pointer to the next node on the same level (Next).

1. connect Function:

• This function traverses the tree level by level, connecting the nodes at each level using the Next pointer.
• First, we check if the root is nil (empty tree), in which case we return nil.
• The currentLevelHead pointer is initially set to the root. This pointer marks the start of each level.
• The outer loop iterates through each level of the tree. The inner loop traverses all the nodes in the current level, connecting the left and right children’s Next pointers.
• After finishing a level, the pointer currentLevelHead is moved down to the leftmost node of the next level.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Where:

• n is the number of nodes in the tree.

Time Complexity:

• The time complexity is O(n) because we visit every node exactly once during the traversal.

Space Complexity:

• The space complexity is O(1) because we only use a constant amount of extra space. The tree is modified in-place without using any additional data structures like a queue or array.

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: []
• Explanation: An empty tree should return nil.

1. Single Node Tree:

• Input: root = [1]
• Output: [1, null]
• Explanation: A tree with a single node has no next node, so the next pointer is set to null.

1. Two-Level Tree:

• Input: root = [1, 2, 3]
• Output: [1, null, 2, null, 3, null]
• Explanation: A two-level tree has two nodes at the second level. The next pointers are set as expected.

Conclusion

LeetCode 116: Populating Next Right Pointers in Each Node is an interesting problem that focuses on linking nodes in a perfect binary tree using their next pointers. We solved this problem using a level-order traversal (BFS) and an optimized in-place approach to avoid using extra space.

This solution runs in O(n) time and uses O(1) space, which is efficient and meets the problem's constraints.