Interview Question for Software Development Engineer In Test (SDET) at Microsoft:

Queue size is never larger than half+1 of the node count, just noting. Rough code:

Queue<T> q = new Queue<T>();
q.Enqueue(root);

int count = 1;
int nextCount = 0;
T prev = null;

while (!q.Empty())
{
  T cur = q.Dequeue();

  if (prev != null)
  {
    // doubly-link level siblings
    prev.rightSibling = cur;
    cur.leftSibling = prev;
  }

  count--;

  if (count == 0)
  {
    // next level
    count = nextCount;
    nextCount = 0;
    prev = null;
  }
  else
  {
    // same level
    prev = cur;
  }

  if (cur.Left != null)
  {
    nextCount++;
    q.Enqueue(cur.Left);
  }

  if (cur.Right != null)
  {
    nextCount++;
    q.Enqueue(cur.Right);
  }
}