{x}
blog image

Populating Next Right Pointers in Each Node

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

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *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.

 

Example 1:

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 in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 212 - 1].
  • -1000 <= Node.val <= 1000

 

Follow-up:

  • You may only use constant extra space.
  • The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

116. Populating Next Right Pointers in Each Node

Problem Description

Given a perfect 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.

Solutions

Two approaches are presented here: Breadth-First Search (BFS) and Depth-First Search (DFS).

Solution 1: Breadth-First Search (BFS)

This approach uses a queue to perform a level-order traversal of the tree. For each level, it iterates through the nodes, linking each node's next pointer to the next node in the level.

Algorithm:

  1. Initialization: If the root is NULL, return NULL. Otherwise, enqueue the root into a queue.
  2. Level Traversal: While the queue is not empty:
    • Get the number of nodes in the current level (size of the queue).
    • Iterate size times:
      • Dequeue a node from the queue.
      • If there's a previous node (p), link its next pointer to the current node.
      • Update p to the current node.
      • Enqueue the node's left and right children (if they exist).
  3. Return: Return the root node.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.

Space Complexity: O(W), where W is the maximum width of the tree (which is equal to 2h for a perfect binary tree of height h). In the worst-case scenario for a perfect binary tree, this is O(N).

Solution 2: Depth-First Search (DFS)

This solution uses recursion to traverse the tree in a depth-first manner. It recursively connects the next pointers within each level.

Algorithm:

  1. Helper Function dfs(left, right): This recursive function takes two nodes (left and right) as input, representing the left and right children of a parent node.
  2. Base Case: If either left or right is NULL, return.
  3. Connection: Set left.next to right.
  4. Recursive Calls: Recursively call dfs for the following pairs:
    • (left.left, left.right)
    • (left.right, right.left)
    • (right.left, right.right)
  5. Main Function: If the root is not NULL, call dfs(root.left, root.right).

Time Complexity: O(N), where N is the number of nodes. Each node is visited and processed once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In a perfect binary tree, H = log₂N, so the space complexity is O(log N).

Code Examples

The following code examples demonstrate both BFS and DFS solutions in several programming languages. Note that the Node structure definition might need to be adapted depending on the specific environment.

(Note: Code examples for Python, Java, C++, Go, and TypeScript are provided in the original prompt response.)

Conclusion

Both BFS and DFS approaches solve the problem with a time complexity of O(N). However, BFS has a space complexity of O(N) in the worst case (for a perfect binary tree), while DFS has a space complexity of O(log N) for a perfect binary tree. Therefore, DFS is generally more space-efficient for this problem, especially for very wide trees. Choose the solution based on your specific needs and constraints.