Link all the nodes at the same level for a binary tree

Problem: Given a binary tree, assume you have one extra pointer (TreeNode *next), link all the nodes at the same level by using this next pointer. No other extra space is allowed (e.g., queue)


Solution:  if the tree is a full binary tree, where all non-leaf nodes have two children, the solution will be easier. You can find it at ihas1337code. If the tree is not necessarily a full binary tree, the solution is more difficult. But here we can still give an iterative solution. The key here is to leverage the established "next" pointer. When we are visiting the ith level (assume all the "next" pointers at ith level have been established), we construct the the "next" pointers at i+1th level. The details of the algorithm are as follow:

• if a node has both left child and right child, then left child's next should link to right child. This is the most straightforward case.
• if a node only have one child, to assign the child's next, we need to look at the node's siblings. basically, we need to find the first non-leaf sibling of the node, then find its left-most child as the target of the current node's child's next pointer. 
• We construct the next pointer level by level. When we are visiting the ith level (assume all the "next" pointers at ith level have been established), we construct the the "next" pointers at i+1th level. During this process, we also record the first non-leaf node at i+1th level. Since when we proceed to visit i+1th level, we need to start from that node. If such node can't be found, it means we finish linking the tree by level.

 The code is as follow (may not be the optimal):

typedef struct TreeNode{
        struct TreeNode *left;
        struct TreeNode *right;
        struct TreeNode *next;
        int value;     
}TreeNode;


bool isLeaf(TreeNode *root)
{
    return root->left==NULL && root->right==NULL;
}

TNode * leftmostChild(TreeNode *root)
{
  return root->left? root->left:root->right;
}


TreeNode * real_next_non_leaf(TreeNode *root)
{
    while(root->next && isLeaf(root->next)) root = root->next;
    
    return root->next;

}

void link_tree_level(TreeNode *root)
{
     if(!root || !isLeaf(root)) return;
     
     TreeNode *firstp = leftmostChild(root);
     
     while(true)
     {
         TreeNode *nnext;
         while(root)
         {
             if(root->left && !root->left->next) 
             {
               if(root->right)  
               {
                  root->left->next = root->right;
                  nnext = real_next_non_leaf(root);
                  root->right->next = nnext ? leftmostChild(nnext) : nnext;
                  root = nnext;              
               }
               else
               {
                  nnext = real_next_non_leaf(root);
                  root->left->next = nnext ? leftmostChild(nnext) : nnext;
                  root = nnext;
               }
             }
             else if(root->right)  
             {
                  nnext = real_next_non_leaf(root);
                  root->right->next = nnext ? leftmostChild(nnext) : nnext;
                  root = nnext;              
            }
         }
                
       
        while(firstp && isLeaf(firstp))
                    firstp = firstp->next;
       
        if(!firstp) break;
        root = firstp;
        firstp = leftmostChild(root);
       
     }
 
}