Problem: Given a binary tree populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
You may assume that it is a perfect binary tree (i.e. all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5-> 6->7 -> NULL
Solution:
Implementation (Recursive approach):
public void connectTree(TreeNode root) {
if(root==null){
return;
}
if(root.left!=null){
root.left.next = root.right;
}
if(root.right!=null){
if(root.next!=null){
root.right.next = root.next.left;
}
else{
root.right.next = null;
}
}
connectTree(root.left);
connectTree(root.right);
}
Non-Recursive approach:
Recursive solution isn’t constant memory, but O(log(n)) memory. To solve this, you just replace the recursive call with a while loop placing all of your logic.
public void connectTree(TreeNode root)
{
while(root != null)
{
TreeNode ptr = root;
while(ptr != null)
{
if(ptr.left != null)
ptr.left.next = ptr.right;
if(ptr.right != null && ptr.next != null)
ptr.right.next = ptr.next.left;
ptr = ptr.next;
}
root = root.left;
}
}
Time Complexity: O(N), Where N is number of nodes in a tree.
Please write/comment if you find anything incorrect.
This article is contributed by Vishwas Garg and edited by crazyforcode team. You can also contribute by writing and mail it to us: [email protected].
void updatingNextPointers(node *root) {
deque q;
int nodect = 0;
q.push_back(root);
while (!q.empty()) {
nodect = q.size();
while (nodect > 0) {
node *k = q.front();
q.pop_front();
nodect–;
if (nodect > 0)
k->next = q.front();
if (k->left)
q.push_back(k->left);
if (k->right)
q.push_back(k->right);
}
}
}
void printNextPointers(node *root) {
if (!root)
return;
cout<val<next);
printNextPointers(root->left);
printNextPointers(root->right);
}
Complexity: O(N)