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.
1class Node {
2public:
3 int val;
4 Node* left;
5 Node* right;
6 Node* next;
7
8 Node() : val(0), left(NULL), right(NULL), next(NULL) {}
9 Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
10};
11
12class Solution {
13public:
14 Node* connect(Node* root) {
15 if (!root) return NULL;
16 Node* current = root;
17 while (current->left) {
18 Node* head = current;
19 while (head) {
20 head->left->next = head->right;
21 if (head->next) head->right->next = head->next->left;
22 head = head->next;
23 }
24 current = current->left;
25 }
26 return root;
27 }
28};This C++ solution uses 'current' to traverse each level, and 'head' to travel across nodes in each level, connecting left to right and next to left of the succeeding nodes. The process moves downwards.
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
Using Python, this code adopts recursion to connect nodes, ensuring each level progresses with accurately distributed next pointers, thanks to the inherent recursive nature.