Populating Next Right Pointers in Each Node II

---

Populating Next Right Pointers in Each Node II: 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 1:

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.

---

Example 2:

Input: root = []
Output: []

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

1. Populating Next Right Pointers in Each Node
2. Binary Tree Right Side View
3. Cycle Length Queries in a Tree

Solution:

Java

class Solution {
  public Node connect(Node root) {
      if(root == null) return null;
      Node treeIter = root;

      while(treeIter != null){
          Node levelIter = treeIter;
          while(levelIter != null){
              if(levelIter.left != null){
                  levelIter.left.next = levelIter.right != null ? levelIter.right : findNext(levelIter.next);
              }
              if(levelIter.next != null && levelIter.right != null){
                  levelIter.right.next = findNext(levelIter.next);
              }
              levelIter = levelIter.next;
          }
          treeIter = findNext(treeIter);
      }

      return root;
  }

  private Node findNext(Node root){
      while(root != null){
        if(root.left != null) return root.left;
        else if(root.right != null) return root.right;

        root = root.next;
      }
      return null;
  }
}

JavaScript

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  if (!root) {
    return null;
  }

  let treeIter = root;

  while (treeIter) {
    let levelIter = treeIter;
    while (levelIter) {
      if (levelIter.left) {
        levelIter.left.next = levelIter.right
          ? levelIter.right
          : findNext(levelIter.next);
      }
      if (levelIter.next && levelIter.right) {
        levelIter.right.next = findNext(levelIter.next);
      }
      levelIter = levelIter.next;
    }
    treeIter = findNext(treeIter);
  }

  return root;
};

function findNext(root) {
  while (root) {
    if (root.left) {
      return root.left;
    } else if (root.right) {
      return root.right;
    }
    root = root.next;
  }
  return null;
}

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None

        treeIter = root

        while treeIter:
            levelIter = treeIter
            while levelIter:
                if levelIter.left:
                    levelIter.left.next = levelIter.right if levelIter.right else self.findNext(levelIter.next)
                if levelIter.next and levelIter.right:
                    levelIter.right.next = self.findNext(levelIter.next)
                levelIter = levelIter.next
            treeIter = self.findNext(treeIter)

        return root

    def findNext(self, root):
        while root:
            if root.left:
                return root.left
            elif root.right:
                return root.right
            root = root.next
        return None

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) {
            return nullptr;
        }

        Node* treeIter = root;

        while (treeIter) {
            Node* levelIter = treeIter;
            while (levelIter) {
                if (levelIter->left) {
                    levelIter->left->next = levelIter->right ? levelIter->right : findNext(levelIter->next);
                }
                if (levelIter->next && levelIter->right) {
                    levelIter->right->next = findNext(levelIter->next);
                }
                levelIter = levelIter->next;
            }
            treeIter = findNext(treeIter);
        }

        return root;
    }

private:
    Node* findNext(Node* root) {
        while (root) {
            if (root->left) {
                return root->left;
            } else if (root->right) {
                return root->right;
            }
            root = root->next;
        }
        return nullptr;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

The twist to Populating Next Right Pointers in Each Node is that we can't be sure whether we will have right or left child. We have to search for it using findNext helper function which iterates over the level and tries to find the next right sibling. We utilize the same level traversal and this time for both left and right child we use findNext to find the next sibling. We also use the same function also to find the start of the next level. Since we're traversing over all nodes in the tree we will have O(n) time complexity with constant space complexity (since we don't create any additional data structure).