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.
1public class Node {
2 public int val;
3 public Node left;
4 public Node right;
5 public Node next;
6 public Node() { }
7 public Node(int _val) { val = _val; }
8}
9
10public class Solution {
11 public Node Connect(Node root) {
12 if (root == null) return null;
13 Node current = root;
14 while (current.left != null) {
15 Node head = current;
16 while (head != null) {
17 head.left.next = head.right;
18 if (head.next != null) {
19 head.right.next = head.next.left;
20 }
21 head = head.next;
22 }
23 current = current.left;
24 }
25 return root;
26 }
27}In this C# implementation, each level is processed with connections established between each node's left and right children, and across to the next node's left child.
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
In Java, this recursive solution cascades through the binary tree, leveraging the ongoing structure to correctly implement rightward connections between nodes within recursive stack boundaries.