Sponsored
Sponsored
This approach uses a breadth-first search (BFS) strategy by employing a queue to keep track of nodes at the current level and connect their children nodes from left to right. After processing all nodes on a level, we move to the children (if any), ensuring the next pointers are correctly set.
Time Complexity: O(n), where n is the number of nodes in the tree since each node is enqueued and dequeued once.
Space Complexity: O(n) for the queue in the worst case where the last level of the tree has a maximum number of nodes.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct Node {
5 int val;
6 struct Node *left;
7 struct Node *right;
8 struct Node *next;
9};
10
11struct Queue {
12 struct Node **data;
13 int front, rear, size, capacity;
14};
15
16struct Queue* createQueue(int capacity) {
17 struct Queue* queue = malloc(sizeof(struct Queue));
18 queue->capacity = capacity;
19 queue->front = queue->size = 0;
20 queue->rear = capacity - 1;
21 queue->data = malloc(queue->capacity * sizeof(struct Node*));
22 return queue;
23}
24
25int isEmpty(struct Queue* queue) {
26 return (queue->size == 0);
27}
28
29void enqueue(struct Queue* queue, struct Node* node) {
30 queue->rear = (queue->rear + 1)%queue->capacity;
31 queue->data[queue->rear] = node;
32 queue->size = queue->size + 1;
33}
34
35struct Node* dequeue(struct Queue* queue) {
36 struct Node* node = queue->data[queue->front];
37 queue->front = (queue->front + 1)%queue->capacity;
38 queue->size = queue->size - 1;
39 return node;
40}
41
42void connect(struct Node *root) {
43 if (!root) return;
44 struct Queue* queue = createQueue(6000);
45 enqueue(queue, root);
46 while (!isEmpty(queue)) {
47 int size = queue->size;
48 struct Node *prev = NULL;
49 for (int i = 0; i < size; i++) {
50 struct Node *node = dequeue(queue);
51 if (prev) prev->next = node;
52 prev = node;
53 if (node->left) enqueue(queue, node->left);
54 if (node->right) enqueue(queue, node->right);
55 }
56 if (prev) prev->next = NULL;
57 }
58 free(queue->data);
59 free(queue);
60}
61This code first checks if the tree is empty and returns immediately if so. It initializes a queue to store nodes. For each node processed, the code sets the next pointer to the next node in the level (or NULL if it is the last node). The children of each node are enqueued for processing in the next level.
This approach leverages a two-pointer or head-tail strategy to eliminate the need for extra storage space beyond two pointers. The idea is to work with two nested loops; an outer loop goes level by level, and an inner loop connects nodes within the same level by their next pointers.
Time Complexity: O(n) since each node is processed once.
Space Complexity: O(1), only utilizing a few pointers.
This C approach uses an iterative strategy that does not require a queue. Instead, it uses head to signify the current level's starting node and a pair of pointers, nextHead and prev, to indicate the next level's starting point and moving connector.