Example
Input Tree
A
/ \
B C
/ \ \
D E F
Output Tree
A---> NULL
/ \
B--> C--> NULL
/ \ \
D--> E--> F--> NULL
Method 1 (Extend Level Order Traversal or BFS)
Connect nodes at same level using constant extra space:
This comment has been removed by the author.
ReplyDeleteMethod: 2
ReplyDeletestatic void connectNodes(Node root){
if(root == null) return;
if(root.left == null && root.right == null) return;
if(root.left != null)
{
if(root.right != null) root.left.next = root.right;
else{
if(root.next == null) root.left.next = root.next;
else{ Node tmp = root;
while(tmp != null && tmp.next.left == null && tmp.next.right == null){
tmp = tmp.next;
}
if(tmp == null) root.left.next = null;
else if(tmp.next.left != null) root.left.next = tmp.next.left;
else root.left.next = tmp.next.right;
}
}
}
if(root.right != null)
{
if(root.next == null) root.right.next = null;
else{
Node tmp = root.next;
while(tmp != null && tmp.left == null && tmp.right == null){
tmp = tmp.next;
}
if(tmp == null)
root.right.next = null;
else if(tmp.left != null) root.right.next = tmp.left;
else root.right.next = tmp.right;
}
}
connectNodes(root.left);
connectNodes(root.right);
}