CareerCup

C#:

private void PopulateNextRight(Node node, Node parent)
{
      if(node==null) return;
      if(parent.leftChild==node) node.nextRight=parent.rightChild;
      PopulateNextRight(node.leftChild, node);
      PopulateNextRight(node.rightChild, node);
}

Consider this Binary Tree;

1
              2                         3
        4          5             6          7

We can observe that for a given r, r.left, and r.right. then a) r.left.nextR = r.right.left and b) r.right.nextR = r.nextR.left. So if we traverse the tree in preOrder we can effectively propagate the nextR, hence;

void propagate(Node r){ //begin with r = root
           if(r.left != null){
                if(r.right != null)  r.left.nextR = r.right.left;
               propagate(r.left);
           }
           if(r.right != null) {
                if(r.nextR != null) r.right.nextR = r.nextR.left;
                propagate(r.right);
           }
   }//end

void SetNextRightNode(node* root)
{
if(root)
{
node* dummy = new node(100000);
if(!dummy)
return;

queue<node*,100> q;
q.enqueue(root);
q.enqueue(dummy);

while(q.isEmpty() == false)
{
node* cur = NULL;
node* prev = NULL;
while((cur = q.dequeue()) != dummy)
{
if(cur->left)
q.enqueue(cur->left);
if(cur->right)
q.enqueue(cur->right);

if(prev)
{
prev->nextRight = cur;
}
prev = cur;
}
q.enqueue(dummy);
}
delete dummy;
}
}

void SetNextRightNode(node* root)
{
if(root)
{
node* dummy = new node(100000);
if(!dummy)
return;

queue<node*,100> q;
q.enqueue(root);
q.enqueue(dummy);

while(q.isEmpty() == false)
{
node* cur = NULL;
node* prev = NULL;
while((cur = q.dequeue()) != dummy)
{
if(cur->left)
q.enqueue(cur->left);
if(cur->right)
q.enqueue(cur->right);

if(prev)
{
prev->nextRight = cur;
}
prev = cur;
}
q.enqueue(dummy);
}
delete dummy;
}
}

We can do this with a single depth first traversal and O(log(n)) space. Important thing is to traverse the right subtrees before the left subtrees. For each level of the tree, we keep a pointer to the last visited node in that level of the tree. In the helper function, we just set the rightChild of the current node to the corresponding element in the array and update the element in the array to be the current node so that next time we are visiting a node in that level, we set the rightChild of that node to the correct Node.

void populate(Node* n) {
    vector<Node*> R;
    populateHelper(n, R, 0);
}
void populateHelper(Node* n, vector<Node*> & R, int h) {
    if ( n == NULL ) return; // obvious
    // if we are at this level for the first time, initialize the
    // corresponding element of R with NULL
    if ( h == R.size() ) R.push_back(NULL); 
    n->rightChild = R[h];  // get last visited Node in that level from R
    R[h++] = n;            // update R and increment h
    populateHelper(n->rightChild, R, h); // traverse right subtree first
    populateHelper(n->leftChild, R, h);
}

void SetSibling(treenode* root)
{
if(root == NULL)
return;
else
{
// Set the siblings
treenode* candidate = NULL;
if(root->left == NULL)
{
if(root->right == NULL)
candidate = NULL;
else
candidate = root->right;
}
else
{
if(root->right == NULL)
candidate = root->left;
else
{
root->left->sibling = root->right;
candidate = root->right;
}
}
treenode* ptr = root->sibling;
treenode* result = NULL;
if(candidate)
{
while(ptr!=NULL)
{
if(ptr->left != NULL)
{
result = ptr->left;
break;
}
else if(ptr->right != NULL)
{
result = ptr->right;
break;
}
ptr = ptr->sibling;
}
candidate->sibling = result;
}
SetSibling(root->right);
SetSibling(root->left);
}
}

@ashish can u plzz explain what u r doing

i am not getting what you want ,please give an example

void connect(struct node *p)
   {
      if(p == NULL)
         return;
   
      if(p -> left)
         p -> left -> nextright = p -> right;
   
      if(p -> right)
         p -> right -> nextright = (p -> nextright) ? p -> nextright -> left : NULL;
   
      connect(p -> left);
      connect(p -> right);
   }