algoadvance

Leetcode 116. Populating Next Right Pointers in Each Node

Problem Statement

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The tree is represented as follows:

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":"4","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"5","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"3","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
Output: {"$id":"1","left":{"$id":"2","left":{"$id":"4","left":null,"next":{"$id":"5"},"right":null,"val":4},"next":{"$id":"3"},"right":{"$id":"5","left":null,"next":{"$id":"6"},"right":null,"val":5},"val":2},"next":null,"right":{"$id":"3","left":{"$id":"6","left":null,"next":{"$id":"7"},"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Strategy

  1. Level Order Traversal: Start from the root node and traverse each level of the tree.
  2. Connections within Levels: For each node, connect its left child to its right child.
  3. Connections across Levels: If the node has a next node (i.e., it is not the rightmost node at its level), connect its right child to the left child of the next node.

By leveraging the properties of a perfect binary tree, we can establish these connections using a pointer to traverse nodes at each level.

Code

#include <iostream>
using namespace std;

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 NULL;

        Node* leftmost = root;

        while (leftmost->left) {
            Node* head = leftmost;

            while (head) {
                head->left->next = head->right;
                if (head->next) {
                    head->right->next = head->next->left;
                }
                head = head->next;
            }
            leftmost = leftmost->left;
        }

        return root;
    }
};

Time Complexity

This algorithm is optimal because it leverages the structure of the perfect binary tree and creates the required connections by only traversing the tree once in a level-order fashion.

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