CareerCup

bfs

struct 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;
}
}

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;
                }
            }
        }

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)

dint understand d question can anyone give me an example??

Actually it is a level order traversal problem. Use a queue or two stacks to implement it.
First enqueue the root, mark the level as 0, then start the loop, dequeue all nodes from queue that on the same level, and chain these nodes together.

#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);

using a queue to store the nodes of a level, while keep the level of each node.
do layer first search
while the head node of queue is at the right level - 1, you know how to do it

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);
	}
	
}

i was asked the same question by STB team. Though i told him BFS solution, he said that BFS was an easy solution, he wanted an iterative solution. i screwed it up badly and lost time and rejected. so try for iterative solution as well.

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;
}