117. Populating Next Right Pointers in Each Node II

leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Populating Next Right Pointers in Each Node II - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

솔루션2로 풀도록 할것.

Given a binary treestruct Node { int val; Node *left; Node *right; Node *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.

Follow up:

You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

The number of nodes in the given tree is less than 6000.
-100 <= node.val <= 100

Solution

Approach 1: Level Order Traversal

Intuition

There are two basic kinds of traversals on a tree or a graph. One is where we explore the tree in a depth first manner i.e. one branch at a time. The other one is where we traverse the tree breadth-wise i.e. we explore one level of the tree before moving on to the next one. For trees, we have further classifications of the depth first traversal approach called preorder, inorder, and the postorder traversals. Breadth first approach to exploring a tree is based on the concept of the level of a node. The level of a node is its depth or distance from the root node. We process all the nodes on one level before moving on to the next one.

Now that we have the basics out of the way, it's pretty evident that the problem statement strongly hints at a breadth first kind of a solution. We need to link all the nodes together which lie on the same level and the level order or the breadth first traversal gives us access to all such nodes which lie on the same level.

Algorithm

Initialize a queue, Q which we will be making use of during our traversal. There are multiple ways to implement the level order traversal especially when it comes to identifying the level of a particular node.
1. We can add a pair of (node, level) to the queue and whenever we add the children of a node, we add \text (node.left, \;\; parent\_level + 1) and (node.right,\;\; parent\_level + 1). This approach wouldn't be very efficient for our algorithm since we need all the nodes on the same level and we would need another data structure just for that.
2. A more memory efficient way of segregating the same level nodes is to use some demarcation between the levels. Usually, we insert a NULL entry in the queue which marks the end of the previous level and the start of the next level. This is a great approach but again, it would still consume some memory proportional to the number of levels in the tree.
3. The approach we will be using here would have a nested loop structure to get around the requirement of a NULL pointer. Essentially, at each step, we record the size of the queue and that always corresponds to all the nodes on a particular level. Once we have this size, we only process these many elements and no more. By the time we are done processing size number of elements, the queue would contain all the nodes on the next level. Here's a pseudocode for the same:
  while (!Q.empty()) { size = Q.size() for i in range 0..size { node = Q.pop() Q.push(node.left) Q.push(node.right) } }
We start off by adding the root of the tree in the queue. Since there is just one node on the level 0, we don't need to establish any connections and can move onto the while loop.
The first while loop from the pseudocode above essentially iterates over each level one by one and the inner for loop iterates over all the nodes on the particular level. Since we have access to all the nodes on the same level, we can establish the next pointers easily.
When we pop a node inside the for loop from the pseudocode above, we add its children at the back of the queue. Also, the element at the head of the queue is the next element in order, on the current level. So, we can easily establish the new pointers.

class Solution {
    public Node connect(Node root) {
        
        if (root == null) {
            return root;
        }
        
        // Initialize a queue data structure which contains
        // just the root of the tree
        Queue<Node> Q = new LinkedList<Node>(); 
        Q.add(root);
        
        // Outer while loop which iterates over 
        // each level
        while (Q.size() > 0) {
            
            // Note the size of the queue
            int size = Q.size();
            
            // Iterate over all the nodes on the current level
            for(int i = 0; i < size; i++) {
                
                // Pop a node from the front of the queue
                Node node = Q.poll();
                
                // This check is important. We don't want to
                // establish any wrong connections. The queue will
                // contain nodes from 2 levels at most at any
                // point in time. This check ensures we only 
                // don't establish next pointers beyond the end
                // of a level
                if (i < size - 1) {
                    node.next = Q.peek();
                }
                
                // Add the children, if any, to the back of
                // the queue
                if (node.left != null) {
                    Q.add(node.left);
                }
                if (node.right != null) {
                    Q.add(node.right);
                }
            }
        }
        
        // Since the tree has now been modified, return the root node
        return root;
    }
}

Complexity Analysis

Time Complexity: since we process each node exactly once. Note that processing a node in this context means popping the node from the queue and then establishing the next pointers.
Space Complexity: . This is a perfect binary tree which means the last level contains nodes. The space complexity for breadth first traversal is the maximum space occupied and the space occupied by the queue is dependent upon the maximum number of nodes in particular level. So, in this case, the space complexity would be .

Approach 2: Using previously established next pointers

Intuition

We have to process all the nodes of the tree. So we can't reduce the time complexity any further. However, we can try and reduce the space complexity. The reason we need a queue here is because we don't have any idea about the structure of the tree and the kind of branches it has and we need to access all the nodes on a common level, together, and establish connections between them.

Once we are done establishing the next pointers between the nodes, don't they kind of represent a linked list? After the next connections are established, all the nodes on a particular level actually form a linked list via these next pointers. Based on this idea, we have the following intuition for our space efficient algorithm:

우리는 나무의 모든 노드를 처리해야 한다. 그래서 우리는 더 이상 시간 복잡성을 줄일 수 없다. 하지만, 우리는 공간 복잡성을 줄이려고 노력할 수 있다. 여기서 대기열이 필요한 이유는 나무의 구조와 가지 종류에 대해 전혀 알 수 없고 모든 노드에 공통적인 차원에서 접근하여 서로 연결해야 하기 때문이다.노드 사이에 다음 포인터를 설정하는 작업을 마치면 노드들이 링크된 목록을 나타내지 않는가? 다음 연결이 설정된 후, 특정 수준의 모든 노드는 실제로 이러한 다음 포인터를 통해 링크된 목록을 형성한다. 이러한 생각을 바탕으로 우리는 공간 효율적인 알고리즘에 대해 다음과 같은 직관을 가지고 있다.

We only move on to the level N+1 when we are done establishing the next pointers for the level N. So, since we have access to all the nodes on a particular level via the next pointers, we can use these next pointers to establish the connections for the next level or the level containing their children.

우리는 N 레벨에 대한 다음 포인터를 설정해야만 N+1 레벨로 이동한다. 따라서 다음 포인터를 통해 특정 레벨의 모든 노드에 액세스할 수 있기 때문에 다음 레벨의 연결이나 그들의 자녀가 포함된 레벨의 연결을 설정하기 위해 이 다음 포인터를 사용할 수 있다.

Algorithm

We start at the root node. Since there are no more nodes to process on the first level or level 0, we can establish the next pointers on the next level i.e. level 1. An important thing to remember in this algorithm is that we establish the next pointers for a level N while we are still on level N-1 and once we are done establishing these new connections, we move on to N and do the same thing for N+1.
As we just said, when we go over the nodes of a particular level, their next pointers are already established. This is what helps get rid of the queue data structure from the previous approach and helps save space. To start on a particular level, we just need the leftmost node. From there on its just a linked list traversal.
Based on these ideas, our algorithm will have the following pseudocode:
leftmost = root while (leftmost != null) { curr = leftmost prev = NULL while (curr != null) { → process left child → process right child → set leftmost for the next level curr = curr.next } }
Before we proceed with the steps in our algorithm, we need to understand some of the variables we have used above in the pseudocode since they will be important in understanding the implementation.
1. leftmost: represents the corresponding variable on each level. This node is important to discover on each level since this would act as our head of the linked list and we will start our traversal of all the nodes on a level from this node onwards. Since the structure of the tree can be anything, we don't really know what the leftmost node on a level would be. Let's look at a few tree structures and the corresponding leftmost nodes on each level.
  
  Oh, in case you are interested in a fun problem that find out all such nodes (rightmost instead of leftmost), check out this problem.
2. curr: As we can see in the pseudocode, this is just the variable we use to traverse all the nodes on the current level. It starts off with leftmost and then follows the next pointers all the way to the very end.
3. prev: This is the pointer to the leading node on the next level. We need this pointer because whenever we update the node curr, we assign prev.next to the left child of curr if one exists, otherwise the right child. When we do so, we also update the prev pointer. Let's consider an example that highlights how the prev pointer is updated. Namely, the following example will highlight the 4 possible scenarios for pointer updates:
  - The first case is when the prev pointer is assigned a non-null value for the very first time i.e. when it is initialized. We start with a null value and when we find the first node on the next level i.e whenever we find the very first node on the current level that has at least one child, we assign the leftmost child to prev.
  - Next is when the node on the current level doesn't have a left child. We then point prev to the right child of the current node. An important thing to remember in this illustration is that the level 2, 3, 5, 9 already has their next pointers properly established.
  - Moving on, we have a node with no children. Here, we don't update the prev pointer.
  - And finally, we come across a node with 2 children. We first update prev to the left child and once the necessary processing is done, we update it to the right child.
Once we are done with the current level, we move on to the next one. One last thing that's left here to update the leftmost node. We need that node to start traversal on a particular level. Think of it as the head of the linked list. This is easy to do by using the prev pointer. Whenever we set the value for prev pointer for the first time corresponding to a level i.e. whenever we set it to it's first node, we also set the head or the leftmost to that node. So, in the following image, leftmost originally was 2 and now it would change to 4.

class Solution {
    
    Node prev, leftmost;
    
    public void processChild(Node childNode) {
        
        if (childNode != null) {
            
            // If the "prev" pointer is alread set i.e. if we
            // already found atleast one node on the next level,
            // setup its next pointer
            if (this.prev != null) {
                this.prev.next = childNode;
                    
            } else {
                
                // Else it means this child node is the first node
                // we have encountered on the next level, so, we
                // set the leftmost pointer
                this.leftmost = childNode;
            }    
                
            this.prev = childNode; 
        }
    }
        
    public Node connect(Node root) {
        
        if (root == null) {
            return root;
        }
        
        // The root node is the only node on the first level
        // and hence its the leftmost node for that level
        this.leftmost = root;
        
        // Variable to keep track of leading node on the "current" level
        Node curr = leftmost;
        
        // We have no idea about the structure of the tree,
        // so, we keep going until we do find the last level.
        // the nodes on the last level won't have any children
        while (this.leftmost != null) {
            
            // "prev" tracks the latest node on the "next" level
            // while "curr" tracks the latest node on the current
            // level.
            this.prev = null;
            curr = this.leftmost;
            
            // We reset this so that we can re-assign it to the leftmost
            // node of the next level. Also, if there isn't one, this
            // would help break us out of the outermost loop.
            this.leftmost = null;
            
            // Iterate on the nodes in the current level using
            // the next pointers already established.
            while (curr != null) {
                
                // Process both the children and update the prev
                // and leftmost pointers as necessary.
                this.processChild(curr.left);
                this.processChild(curr.right);
                
                // Move onto the next node.
                curr = curr.next;
            }
        }
                
        return root ;
    }
}

Complexity Analysis

Time Complexity: O(N) since we process each node exactly once.
Space Complexity: O(1) since we don't make use of any additional data structure for traversing nodes on a particular level like the previous approach does.