The beauty of algorithm

Consider this problem. For every node of a given binary tree, add a new pointer "next" to it and let it point to the next node at the same level. In another words, create a linked list fo each level at the binary tree. I.e. for the below binary tree.

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

You will end up with 4 lists:

• 3 -> NULL
• 5 -> 1-> NULL
• 6 -> 2 -> 0->8 -> NULL
• 7->4-> NULL

This looks like a variant of a BFS problem. We just do a BFS for this binary tree, but how do we differ the node at each level? A slightly change to the BFS algorithm will do. Basically we add a level information to the node in the queue.  Check code below

void SetTreeNext(Node * root) 
{ 
    typedef std::pair NodeData;
    std::list queue;
    int prevLevel = 0;
    Node * prevNode;
    queue.push_back (NodeData(root, 1));

    while (!queue.empty())
    {
        NodeData data = queue.front();
        Node * curNode = data.first;
        int curLevel = data.second;
        queue.pop_front();
        
        if (curLevel != prevLevel)
        {
            prevNode = curNode; 
        }
        else 
        {
            prevNode->next = curNode;
        }
        if (curNode->left) 
            queue.push_back (NodeData(curNode->left, curLevel +1) );
        if (curNode->right) 
            queue.push_back (NodeData(curNode->right, curLevel +1) );
    }
} 

Time complicity O(N). Space complicity O(N)

Method 2:

Could we do it without the level information? Yes of course. We could track the number of nodes at current level and previous level. But here we will present a different solution.

Consider we do a normal BFS, the result looks like this:

 3-> 5 -> 1 -> 6 -> 2 -> 0 -> 8 -> 7 ->4

If we have a NULL pointer at the end of each level, the BFS will look like this:

3 -> NULL -> 5 -> 1 -> NULL -> 6 ->2 ->0 ->8 -> NULL -> 7 -> 4 -> NULL

The question is can we convert the first BFS result to the next one? Let's do it level by level.

First we have root information stored in the list

3 -> NULL

We keep a current pointer (starts with the first pointer for every level), now it points to 3. We start from this current pointer and put all its children to the end of list; then the current pointer moves to the next pointer until it sees a NULL (end of the current level). At this moment we know we are done to put children of current level at the end of list; we can put a NULL at the end of this.

3 -> NULL -> 5 -> 1 -> NULL

Repeat this process we can get the final list. For every node in this list, we can start to chain them. For every NULL node, we start with a new level.

Time complicity O(N). Space complicity O(N)

Method 3:

We presented two methods with O(N) time and O(N) space. We could not do any better in terms of time complexity since we need to visit each node at least once. Could we do it better in terms of space?  Here is an interesting one with O(1) space. 

We have a new pointer 'next' in each node. Could this pointer help us in the tree search? Consider at first level we have:

     root (3) -> NULL
For next level, we started with one of the children of the first level, in this case it is 5 (left child of 3). What is 5's next node? It could have a few possibilities:

if 5's parent node has a right child, the next node should be parent node's right child
if the node itself is the right child or the parent does not have aright child (i.e. at third level, 6->2->0->8->NULL, node 2). In this case, we will go to next node of its parent node and find its first child. What if no child? Continue to search the next chain!


Repeat this process we can chain all the nodes at the same level without any additional space.



Check code below

void SetNextNode (node * root)

{
    if (!root || (!root->left && ! root->right)) return;

    // start node of current level
    node * startNode  = root->left ? root->left : root->right;
    node * parentNode = root;
    while (true)
    {
        // process current level
        Node * currentStartNode = startNode;
        while (parentNode)
        {
            // The next child is the right sibling of current node
            if (parentNode->left == startNode && parentNode->right) 
            {
                startNode->next = parentNode->right;
                startNode = parentNode->right;
            }
            else if (parentNode->right == startNode || 
                   (! parentNode->left && !parentNode->right) )
            {
                // go to next node in parent's chain
                parentNode = parentNode->next;
            }
            else 
            {
                Node * nextNode = parentNode->left ? parentNode->left : parentNode->right;
                startNode->node  = nextNode;
                startNode = nextNode;
            }
        }

        // find first available child in current level
        while (currentStartNode && !currentStartNode->left && !currentStartNode->right) 
            currentStartNode = currentStartNode->next;
 
        if (!currentStartNode) break;
        parentNode = currentStartNode;
        startNode = parentNode->left? parentNode->left: parentNode->right;
    }
}