...

/

Connect Level Order Siblings (medium)

Connect Level Order Siblings (medium)

Problem Statement

Given a binary tree, connect each node with its level order successor. The last node of each level should point to a null node.

Example 1:

Example 2:

Try it yourself

Try solving this question here:

import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode next;
TreeNode(int x) {
val = x;
left = right = next = null;
}
// level order traversal using 'next' pointer
void printLevelOrder() {
TreeNode nextLevelRoot = this;
while (nextLevelRoot != null) {
TreeNode current = nextLevelRoot;
nextLevelRoot = null;
while (current != null) {
System.out.print(current.val + " ");
if (nextLevelRoot == null) {
if (current.left != null)
nextLevelRoot = current.left;
else if (current.right != null)
nextLevelRoot = current.right;
}
current = current.next;
}
System.out.println();
}
}
};
class ConnectLevelOrderSiblings {
public static void connect(TreeNode root) {
// TODO: Write your code here
}
public static void main(String[] args) {
TreeNode root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.left.left = new TreeNode(9);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(5);
ConnectLevelOrderSiblings.connect(root);
System.out.println("Level order traversal using 'next' pointer: ");
root.printLevelOrder();
}
}

Solution

This problem follows the Binary Tree Level Order Traversal pattern. We can follow the same BFS approach. The only difference is that while traversing a level we will remember the previous node to connect it with the current node. ...