Practice/Meta/Leetcode 116. Populating Next Right Pointers in Each Node

Leetcode 116. Populating Next Right Pointers in Each Node

CodingMust

Problem

You are given a perfect binary tree where every parent node has exactly two children, and all leaf nodes are at the same depth. Each node in the tree has an additional pointer called next that is initially set to null.

Your task is to populate the next pointer of each node to point to its immediate right neighbor at the same level. If there is no right neighbor, the next pointer should remain null.

After connecting all nodes, return the root of the modified tree.

Requirements

1. Connect each node's next pointer to the node immediately to its right at the same level
2. The rightmost node at each level should have its next pointer set to null
3. Modify the tree in-place and return the root
4. Handle edge cases like empty trees and single-node trees
5. The tree is guaranteed to be a perfect binary tree

Constraints

• The number of nodes in the tree is in the range [0, 2^12 - 1]
• -1000 <= Node.val <= 1000
• The tree is a perfect binary tree (all internal nodes have two children and all leaves are at the same level)
• You should use constant extra space (O(1) space complexity, not counting recursion stack)

Examples

Example 1:

` Input: 1 /
2 3 / \ /
4 5 6 7

Output: 1 -> null /
2 -> 3 -> null / \ /
4->5->6->7 -> null

Explanation: After connecting, node 2's next points to 3, node 4's next points to 5, node 5's next points to 6, and node 6's next points to 7. `

Example 2:

` Input: 1

Output: 1 -> null

Explanation: Single node has no right neighbor, so next remains null. `

Example 3:

` Input: null

Output: null

Explanation: Empty tree returns null. `