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 public int val;
public Node left;
public Node right;
public Node next;
public Node() { }
public Node(int _val) { val = _val; }
}
public class Solution {
public Node Connect(Node root) {
if (root == null || root.left == null)
return root;
root.left.next = root.right;
if (root.next != null)
root.right.next = root.next.left;
Connect(root.left);
Connect(root.right);
return root;
}
}This C# recursive implementation handles each subtree similarly, employing the stack to manage the sequence of operations in node connectivity.