Microsoft Interview Question
Software Engineer / DevelopersCountry: India
private static void InitNext(TreeNode root)
{
if(root == null) return;
var mainQueue = new Queue<TreeNode>();
var childQueue = new Queue<TreeNode>();
TreeNode first = null;
mainQueue.Enqueue(root);
while (mainQueue.Count > 0)
{
var temp = mainQueue.Dequeue();
if(first == null)
{
first = temp;
}
else
{
first.Next = temp;
first = temp;
}
if (temp.Left != null)
childQueue.Enqueue(temp.Left);
if (temp.Right != null)
childQueue.Enqueue(temp.Right);
if (mainQueue.Count == 0)
{
while (childQueue.Count > 0)
{
mainQueue.Enqueue(childQueue.Dequeue());
}
first = null;
}
}
}
I wrote exactly the same with slight modification.
private static void InitNext(TreeNode root)
{
if(root == null) return;
var mainQueue = new Queue<TreeNode>();
var childQueue = new Queue<TreeNode>();
TreeNode first = null;
mainQueue.Enqueue(root);
while (mainQueue.Count > 0)
{
var temp = mainQueue.Dequeue();
if (temp.Left != null)
childQueue.Enqueue(temp.Left);
if (temp.Right != null)
childQueue.Enqueue(temp.Right);
if (mainQueue.Count == 0)
{
temp= childQueue.Dequeue();
mainQueue.Enqueue(temp);
while (childQueue.Count > 0)
{
TreeNode second = childQueue.Enqueue();
temp.next = second;
temp = second;
mainQueue.Enqueue(second);
}
}
}
}
Use two queues Q1 and Q2 and the concept of Breadth first search
writing a pseudo-code below
Q1.enqueue(root)
e1 = NULL
While ( !(Q1.isEmpty() && Q2.isEmpty()) ) {
if (e1 == NULL)
e1 = Q1.dequeue() // handling the root
if (e1 == NULL) {
For all elements in Q2 : Q1.enqueue(Q2.dequeue())
else {
e2 = Q1.dequeue()
e1.special_ptr = e2
Q2.enqueue(e1)
e1 = e2
}
}
A similar solution using recursion(C#):
The signature of the mathod is like: void SetNextPointer(ref Node child,ref Node root)
Logic:
1. if child==null or root==null then return
2. Node nextLevel=null,startRoot=null (nextLevel is used to record the left most node of next level while startRoot is used to record the parent of nextLevel)
3. Node p=root,q=child
4. while p!=null do 5-6
5. if nextLevel has not been set and q has child then we set nextLevel as the left most child of q
6. if p has left child and p's left child is not q then we set q.Next as p.LChild and set q as q.Next; else if p has rchild then we set q.Next=q.RChild and q=q.Next and p=p.Next
7. recursion call SetNextPointer(ref nextLevel, ref startRoot)
#include <queue>
using namespace std;
struct TREE_NODE
{
int nValue;
TREE_NODE** ppChildren;
int nNumOfChildren;
TREE_NODE* pSibling;
}
struct QNODE
{
TREE_NODE* pTreeNode;
int nLevel;
}
void ChainSiblings(TREE_NODE* root)
{
if (root == NULL)
{
return;
}
// Enqueue root node.
std::queue<QNODE*> q;
QNODE* r = new QNODE;
r->pNode = root;
r->nLevel = 0;
q.push(r);
while(q.size() > 0)
{
int nCurLevel = (q.front())->nLevel;
while ((q.front())->nLevel == nCurLevel)
{
QNODE* pCurNode = q.pop();
if (pCurNode->pTreeNode->ppChildren != NULL)
{
assert(pCurNode->pTreeNode->nNumOfChildren > 0);
for (int i=0; i<pCurNode->pTreeNode->nNumOfChildren; ++i)
{
QNODE* pChild = new QNODE;
pChild->pTreeNode = pCurNode->pTreeNode->ppChildren[i];
pChild->nLevel = pCurNode->pTreeNode->nLevel + 1;
q.push(pChild);
}
}
QNODE* head = q.front();
if (pCurNode->nLevel == head->nLevel)
{
pCurNode->pTreeNode->pSibling = head->pTreeNode;
}
else
{
pCurNode->pTreeNode->pSibling = NULL;
}
delete pCurNode;
}
}
}
What about maintaining of pointer's list?
#include <vector>
using std::vector;
struct Node{
int n_child;
Node **child;
Node *sibling; // NULL by description
};
vector<Node *> last_sibling;
void resolveSibling (Node *node, int level)
{
if (last_sibling.size() < level + 1)
{
last_sibling.push_back (node);
}
else
{
last_sibling[level]->sibling = node;
last_sibling[level] = node;
}
for (int i = 0 ; i < node->n_child ; i++)
{
resolveSibling(node->child[i], level+1);
}
}
resolveSibling (root, 0);
static node * queue[50];
int index = 0;
void level_print(int d,int l,node *root){
if(!root || d > l) return;
if(d == l)
queue[index++] = root;
d++;
print_level(d,l,root->left);
print_level(d,l,root->right);
}
void assign_next_node_pointer)
{
int h = height_of_tree;
node *root = root_of_tree;
for(i = 1 ; i <=h;i++)
{
print_level(0,i,root);
k = 1;
while(k < index){
queue[k-1] - >next_level_node = queue[k];
}
index = 0 ; //for next level iteration
}
}
}
class PrepareBT{
public static void main(String[] args) {
prepareBT(root);
}
public void prepareBT(Node* node){
Node * temp=node;
Node * current=null;
Node * nextLevelNode = null;
while(temp!=null){
if(temp->left!=null){
current = temp->left;
nextLevelNode = current;
if (temp->right!=null){
current->next =temp->right;
current = temp->right;
}
temp = temp->next;
break;
}else if (temp->right!=null){
current = temp->right;
nextLevelNode = current;
temp = temp->next;
break;
}
}
while(temp!=null){
if(temp->left!=null){
current->next =temp->left;
current = temp->left;
}
if(temp->right!=null){
current->next =temp->right;
current = temp->right;
}
temp = temp->next;
}
prepareBT(nextLevelNode);
}
}
There is no need to have recursion nor queue. The code should take O(n) time and O(1) space.
struct STN
{
int Value;
STN *Left;
STN *Right;
STN *Sibling;
};
void PopulateSibling(STN* root)
{
STN* current = root;
STN* nextFirst = nullptr;
STN* nextLast = nullptr;
while(current != nullptr)
{
for( ; current != nullptr; current = current->Sibling)
{
STN* children[] = {current->Left, current->Right};
for (int i = 0; i < ARRAY_LENGTH(children); i++)
{
if (children[i] != nullptr)
{
if (nextFirst == nullptr)
{
nextFirst = children[i];
nextLast = children[i];
}
else
{
nextLast->Sibling = children[i];
nextLast = children[i];
}
}
}
}
current = nextFirst;
nextFirst = nullptr;
nextLast = nullptr;
}
}
TreeNode* AddSibPtr(TreeNode* root)
{
std::queue<TreeNode*> q;
TreeNode* Pre = NULL;
TreeNode* N= NULL;
if( root == NULL )
return NULL;
if( root->left != NULL )
q.push( root->left);
if( root->right != NULL )
q.push( root->right);
q.push(NULL);
while( q.size() >= 0 )
{
N = q.front();
q.pop();
if( N == NULL )
if(Pre == NULL)
break;
else
{
Pre->sib = N;
q.push(NULL);
}
else
Pre->sib = N;
if( N != NULL )
{
if( N->left != NULL)
q.push(N->left);
if( N->right != NULL)
q.push(N->right);
}
Pre = N;
}
return root;
}
bfs
- luckycat March 05, 2012struct tnode{
char value;
int flag; //0 means untouched; 1 means in queue; 2 means processed
tnode ** childrenarray;
int degree;
tnode * brother; //the special pointer
int level;
};
void bfs(tnode * r) // assume all 0 nodes
{
queue<tnode *> q;
r->flag=-1;
q.push(r);
tnode * curr;
while(!q.empty())
{
curr=q.front();
q.pop();
tnode * child;
for(int i=0;i<curr->degree;i++)
{
child=curr->childrenarray[i];
if(child!=NULL&&child->flag==0)
{
child->flag=1;
child->level=curr->level+1;
q.push(child);
}
}
if(!q.empty()&&curr->level==q.front()->level)
curr->brother=q.front();
curr->flag=2;
}
}