Given the root of a binary search tree, link all the nodes at the same level, by using an additional Node* level.

Question

Anonymous · Accepted Answer

Start from the root, 
put all the nodes in a queue,
keep track of number of nodes at current level and at next level by counting,
dequeue a node from the queue, 
put its left and right children in the queue by updating your counts,
using your counts, connect the nodes at the same level.
O(N) in both time and space.

redgiant · Answer

Queue size is never larger than half+1 of the node count, just noting. Rough code:

Queue q = new Queue();
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);
  }
}

Microsoft

Microsoft Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches