Given a perfect binary tree, where each node contains an additional pointer called next. This pointer is initially set to NULL for all nodes. Your task is to connect all nodes of the same hierarchical level by setting the next pointer to its immediate right node. The next pointer of the rightmost node at each level is set to NULL.

populate-next-pointers.js

function populateNextPointers(root) {
  // we traverse the tree level by level by using two variables,
  // left and current

  // left is always the leftmost element of the current level,
  // current starts the same as left, but moves right along the level
  // as soon as current has nowhere to move, we shift level by shifting left down one level, and setting current to the same as left

  // so the algorithm is
  // root is left, current
  // current.left.next = current.right
  // current.next is null, shift level
  // make root.left next, current

  // current.left.next = current.right
  // current.next is not null
  // so current.right.next = current.next.left
  // make current current.next
  // current.left.next = current.right
  // current.next is now null, shift level

  let left = root;
  let current = root;

  while (left) {
    if (current.left) {
      current.left.next = current.right;
    }
    if (current.next) {
      if (current.right) {
        current.right.next = current.next.left;
      }
      current = current.next;
    } else {
      left = left.left;
      current = left;
    }
  }

  return root;
}

export { populateNextPointers };

// tc: O(n)
// sc: O(1)