[LeetCode] Populating Next Right Pointers in Each Node II

Problem: Given a binary tree

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:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above 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.

Input: root = []
Output: []

Approach: We can use Level Order traversal to solve this problem easily and we can use Pre order traversal too but these approaches will take at least O(logn) space.

What we can use is the next pointer itself. We will use kind of level order traversal only but think if before going to next level if we have set the next pointer for the next level already then we will just use the starting node of the level and then we can traverse the whole level using the next pointer.

With this intuition, you can just look at the implementation to understand all the steps.

Implementation in C#:

    public Node Connect(Node root)

    {

        if (root == null)

        {

            return root;

        }

        Node levelStartNode = root;

        while (levelStartNode != null)

        {

            Node currNode = levelStartNode;

            Node prevNode = null;

            levelStartNode = null;

            while (currNode != null)

            {

                if (currNode.left != null)

                {

                    this.UpdateNextNode(currNode.left,

                                    ref prevNode,

                                    ref levelStartNode);

                }

                if (currNode.right != null)

                {

                    this.UpdateNextNode(currNode.right,

                                    ref prevNode,

                                    ref levelStartNode);

                }

                currNode = currNode.next;

            }

        }

        return root;

    }

    private void UpdateNextNode(

                            Node node,

                            ref Node prevNode,

                            ref Node levelStartNode)

    {

        if (prevNode != null)

        {

            prevNode.next = node;

            prevNode = node;

        }

        else

        {

            prevNode = node;

            levelStartNode = node;

        }

    }

Complexity: O(n)