algoadvance

Leetcode 117. Populating Next Right Pointers in Each Node II

Problem Statement

Given a binary tree:

• struct 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.

Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$ref":"4"},"right":null,"val":4},"next":{"$ref":"5"},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"5"},"val":3},"next":null}

Clarifying Questions

1. Is the input guaranteed to be a valid binary tree?
   • Yes, you can assume the input is a valid binary tree.
2. Can the binary tree be empty (null root)?
   • Yes, the binary tree can be empty.
3. Are there any constraints on the size of the binary tree?
   • No specific constraints, but the tree can be large.

Strategy

1. Use a Level Order Traversal (Breadth-First Search).
   • Start with the root node and traverse the tree level by level.
   • Use a queue to keep track of the nodes at each level.
   • For each level, connect nodes from left to right using the next pointers.
2. Handling Nodes without Children:
   • For any node that does not have a child, the next pointer should be set to NULL.

Code

Here is a solution using the described strategy of level order traversal with a queue:

#include <queue>

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        
        std::queue<Node*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            Node* prev = nullptr;
            
            for (int i = 0; i < size; ++i) {
                Node* curr = q.front();
                q.pop();
                
                if (prev) {
                    prev->next = curr;
                }
                prev = curr;
                
                if (curr->left) {
                    q.push(curr->left);
                }
                if (curr->right) {
                    q.push(curr->right);
                }
            }
            
            // The last node of the current level should point to NULL
            if (prev) {
                prev->next = NULL;
            }
        }
        
        return root;
    }
};

Time Complexity

• The time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree.

• This is because each node is processed exactly once in the level-order traversal.

• The space complexity is also O(n) in the worst case, which occurs when the tree is a complete binary tree and the last level has about n/2 nodes. The queue will need to store all these nodes simultaneously.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?