Sponsored
Sponsored
This approach involves using a queue to perform a level order traversal of the tree. At each level of the tree, we'll connect the 'next' pointers of all nodes at that level. Since it is a perfect binary tree, each node at a level is directly followed by its sibling or by NULL if it is the last node at that level.
Time Complexity: O(N), where N is the number of nodes, since each node is processed once.
Space Complexity: O(1), as no extra space other than pointers is used—the perfect use of a constant space solution.
1#include <stdlib.h>
2
3struct Node {
4 int val;
5 struct Node *left;
6 struct Node *right;
7 struct Node *next;
8};
9
10void connect(struct Node* root) {
11 if (!root) return;
12 struct Node* current = root;
13 while (current->left) {
14 struct Node* head = current;
15 while (head) {
16 head->left->next = head->right;
17 if (head->next) {
18 head->right->next = head->next->left;
19 }
20 head = head->next;
21 }
22 current = current->left;
23 }
24}This C code uses a pointer 'current' to iterate levels starting from the root. Another pointer 'head' iterates nodes across a level, connecting left and right children. Each right child's next is connected to the next node's left child, if it exists.
The recursive method explores the tree depth-first and connects nodes level-wise. This approach effectively utilizes the call stack for traversal, aligning with the tree's inherent properties.
Time Complexity: O(N), which implies visiting each node once.
Space Complexity: O(logN) for recursion stack, since depth is proportional to the logarithm of node count.
1
This C function uses recursion to traverse the tree, performing connections between each node's immediate left and right children, and recursively developing connections within each subtree.