LeetCode Populating Next Right Pointers in Each Node I and II: BFS with O(1) Space

Overview

LeetCode Populating Next Right Pointers in Each Node I and II: use the linked list to simulate the role of a queue in BFS with O(1) Space cost.

LeetCode Populating Next Right Pointers in Each Node I and II

(1) Given a binary tree

struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

(2) Follow up for problem “Populating Next Right Pointers in Each Node II“.

What if the given tree could be any binary tree? Would your previous solution still work?

Solution: BFS with O(1) Space

The first problem is not hard because of the very special structure of the perfect tree. I did not go through the “I” problem but just directly head into the second follow up problem since it is more general, once we solve “II”, then “I” is obviously solved too. (BTW, it is also worth thinking about the solution specific to a perfect tree just for practice purpose).

If we are allowed to use additional memory, then we could just maintain two queues and do level-order traversal over the tree (i.e. level by level, each queue store all the nodes in a single level in turn). The idea is still do level order traversal but WITHOUT the additional queue (we are required to use constant memory). Think about how before you continue (hint: pay special attention to the structure of the tree node to see what does it have)

Yes, the memory we need is already there and given! Remember the LinkTreeNode contains the next pointer, the reason we need to store all the elements into a queue using additional memory previously is that we need all of them to get all the nodes in next level. However, we don’t need to store all the elements now, we already can access all the information we need as long as we have the first node in that level. Because we make the list, so every level is a linked list, once we get the head, we get the whole thing, the while information to get all the nodes in next level. So what we need is just constant number of pointers to store the head.  We still simulate the process of the level order traversal (similar to BFS), starting from the root. Now we have the root, so we can pass all the nodes in next level (root’s children) and make the list in that level, and we store the head of the next level, then we are gonna make the list of the third level, since we have the head of the second level list, by going through (list traversal) the second level, we can make the third level, we then store the head of the third level list. We keep doing so until no nodes are left. Note, at all the time, we only need to keep the head of the previous level and the head of the current list of level we are processing.

The following code implements this idea and is accepted by both LeetCode Populating Next Right Pointers in Each Node I and II:

class Solution {

    public:

        void connect(TreeLinkNode *root) {
            if (NULL == root)
                return ;

            root->next = NULL;

            TreeLinkNode *ptr  = NULL;
            TreeLinkNode *curr = root;
            TreeLinkNode *next = NULL;

            while (curr) {

                while (curr) {
                    if (curr->left) {
                        if (ptr) {
                            ptr->next = curr->left;
                            ptr = curr->left;
                        }
                        else {
                            ptr = next = curr->left;
                        }
                        ptr->next = NULL;
                    }
                    if (curr->right) {
                        if (ptr) {
                            ptr->next = curr->right;
                            ptr = curr->right;
                        }
                        else {
                            ptr = next = curr->right;
                        }
                        ptr->next = NULL;
                    }
                    curr = curr->next;
                }
                curr = next;
                next = ptr = NULL;
            }
        }
};

And for the Populating Next Right Pointers in Each Node I, to further utilize the perfect tree property, we can simplify the code because we know the head of the next level, the following code could be accepted by Populating Next Right Pointers in Each Node I but not for II:

void connect(TreeLinkNode *root) {  
    if (NULL == root) 
        return;
    TreeLinkNode *curr = root;
    TreeLinkNode *next = root->left;
    curr->next = NULL;

    while (curr) {
        next = curr->left;
        while (curr) {
            if (curr->left) {
                curr->left->next = curr->right;
                if (curr->next)
                    curr->right->next = curr->next->left;
                else
                    curr->right = NULL;
            }
            curr = curr->next;
        }
        curr = next;
    }
}

Also note although the problems are tagged with DFS from LeetCode, I really do not see any point of DFS because of the constant memory requirement.

Summary

LeetCode Populating Next Right Pointers in Each Node I and II: use the linked list to simulate the role of a queue in BFS with O(1) Space cost.

Written on May 22, 2013