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:
2 def __init__(self, val=0, left=None, right=None, next=None):
3 self.val = val
4 self.left = left
5 self.right = right
6 self.next = next
7
8class Solution:
9 def connect(self, root: 'Node') -> 'Node':
10 if not root:
11 return None
12 current = root
13 while current.left:
14 head = current
15 while head:
16 head.left.next = head.right
17 if head.next:
18 head.right.next = head.next.left
19 head = head.next
20 current = current.left
21 return rootThis Python solution uses two pointers, 'current' for moving level-wise and 'head' for node-wise traversal within a level to connect subsequent next pointers.
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.