Dare2Solve
Given a binary tree, the goal is to populate each node's next
pointer to point to its next right node. If there is no next right node, the next
pointer should be set to null
. The tree can have varying levels of depth, and some nodes might have one or no children.
To connect nodes at the same level, a breadth-first traversal of the tree is ideal because it allows us to process each level of the tree separately. By processing nodes level by level, we can easily link them together using the next
pointer.
Edge Case Handling:
null
or the tree has no children, return the root immediately.Breadth-First Search (BFS):
prevNodeByLevel
) to track the last node visited at each level.Processing Nodes:
next
pointer to the current node.Child Nodes:
Return the Root:
(O(N)), where (N) is the number of nodes in the tree. Each node is visited once.
(O(N)), where (N) is the number of nodes. This accounts for the space used by the queue during BFS and the map used to store the last node at each level.
/*
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
queue<pair<Node*, int>> q;
q.push({root, 0});
unordered_map<int, Node*> prevNodeByLevel;
while (!q.empty()) {
auto [node, level] = q.front();
q.pop();
if (prevNodeByLevel.count(level)) {
prevNodeByLevel[level]->next = node;
}
if (node->left) {
q.push({node->left, level + 1});
}
if (node->right) {
q.push({node->right, level + 1});
}
prevNodeByLevel[level] = node;
}
return root;
}
};
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
queue = [(root, 0)]
prev_node_by_level = {}
while queue:
node, level = queue.pop(0)
if level in prev_node_by_level:
prev_node_by_level[level].next = node
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
prev_node_by_level[level] = node
return root
/*
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
}
*/
class Solution {
public Node connect(Node root) {
if (root == null) return root;
Queue<Pair<Node, Integer>> queue = new LinkedList<>();
Map<Integer, Node> prevNodeByLevel = new HashMap<>();
queue.add(new Pair<>(root, 0));
while (!queue.isEmpty()) {
Pair<Node, Integer> pair = queue.poll();
Node node = pair.getKey();
int level = pair.getValue();
if (prevNodeByLevel.containsKey(level)) {
prevNodeByLevel.get(level).next = node;
}
if (node.left != null) {
queue.add(new Pair<>(node.left, level + 1));
}
if (node.right != null) {
queue.add(new Pair<>(node.right, level + 1));
}
prevNodeByLevel.put(level, node);
}
return root;
}
}
var connect = function (root) {
if (!root || (!root.left && !root.right)) {
return root;
}
let queue = [[root, 0]];
let prevNodeByLevel = new Map();
while (queue.length) {
let [node, level] = queue.shift();
if (prevNodeByLevel.has(level)) {
let prevNode = prevNodeByLevel.get(level);
prevNode.next = node;
}
if (node.left) {
queue.push([node.left, level + 1]);
}
if (node.right) {
queue.push([node.right, level + 1]);
}
prevNodeByLevel.set(level, node);
}
return root;
};