Coderust: Hacking the Coding Interview/

...

/

Connect All Siblings of a Binary Tree

Connect All Siblings of a Binary Tree

Given a binary tree, connect its nodes so that it allows a level-order traversal of the tree.

We'll cover the following...

Statement

The task is to connect all nodes at the same hierarchical level. Connect them from left to right, such that the next pointer of each node points to the node on its immediate right. The next pointer of the right-most node at each level should point to the first node of the next level in the tree.

Each node in the given binary tree for this problem contains the next pointer, along with the left and right pointers. The next pointer is used to connect the same level nodes to each other and across levels.

Example

Consider the following binary tree:

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 75 node1->node4 node5 125 node2->node5 node6 300 node2->node6 node7 10 node3->node7 node9 15 node8 350 node6->node8 node7->node9

Here’s how the final tree looks when all the next pointers are connected:

G root 100 node1 50 root->node1 root->node1 node2 200 root->node2 node1->node2 node3 25 node1->node3 node4 75 node1->node4 node2->node3 node5 125 node2->node5 node6 300 node2->node6 node3->node4 node7 10 node3->node7 node9 15 node4->node5 node5->node6 node6->node7 node8 350 node6->node8 node7->node8                               node7->node9 node8->node9 nullNode5 NULL node9->nullNode5

Sample input

The input list below represents the level-order traversal of the binary tree, while the value that follows represents the node whose next node we need to find:

[100, 50, 200, 25, 75, 125, 300, 10, 350, 15], 200

Expected output

Only if the next pointer of the node with value 200 is correctly set up will the correct result, 25, be returned.

25

Try it yourself

...