Java: Populating Next Right Pointers in Each Node of a Binary Tree

Problem Statement: You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. 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:

Code:

Explanation:

Above is the iterative approach to the problem.

Initialize a queue data structure that would be useful for tree traversal. Initially add root to the queue. Then iterate over each level of the tree.

Iterate over all the nodes on the current level. Remove the node from the front of the queue. The check (i < size-1) is important as we don’t want to establish any wrong connections. The queue will contain nodes from 2 levels at most at any point in time(since we are adding node’s children to the queue). This check ensures we don’t establish the next pointers beyond the end of the current level.

Keep adding the children of a node in the queue and so on…

In the end return the root of the tree with the next pointers populated.

Complexity Analysis:

Time Complexity: O(N), N is the number of nodes in the binary tree since we are visiting every node once.

Space Complexity: O(N).

Github link to the solution: https://github.com/shivanidwivedi/JavaProgramming/commit/0d9d7ea4fcc889c6f31e3ddd28e8f2b5625a9a57