Problem: Connect All Siblings of a Binary Tree

Medium

30 min

Explore how to connect each node of a perfect binary tree to its immediate right sibling using breadth-first search traversal. Understand the problem constraints, develop a clear approach to connect nodes level-wise, and implement an efficient solution running in linear time and constant space. This lesson strengthens your grasp of tree BFS traversal and pointer manipulation techniques essential for coding interviews.

Statement

Given the root of a perfect binary treeA binary tree in which all the levels are completely filled with nodes, and all leaf nodes (nodes with no children) are at the same level., where each node is equipped with an additional pointer, next, connect all nodes from left to right. Do so in such a way that the next pointer of each node points to its immediate right sibling except for the rightmost node, which points to the first node of the next level.

The next pointer of the last node of the binary tree (i.e., the rightmost node of the last level) should be set to NULL.

Constraints:

The number of nodes in the tree is in the range $[0, 500]$ .
$-1000 \leq$ Node.data $\leq 1000$

Connect All Siblings of a Binary Tree

Which node will the next pointer of node $5$ be pointing toward after connecting all the siblings in the given tree?

         _______ 1 _______
        |                  |
     __ 2 _             __ 3__
    |       |          |       |
   _4_    _ 5 _      - 6 -    --7--
  |   |  |     |    |     |  |     |
  8   9  10    11  12    13  14    15

1 / 4

Problem: Connect All Siblings of a Binary Tree

Medium

30 min

Statement

The next pointer of the last node of the binary tree (i.e., the rightmost node of the last level) should be set to NULL.

Constraints:

The number of nodes in the tree is in the range $[0, 500]$ .
$-1000 \leq$ Node.data $\leq 1000$

Connect All Siblings of a Binary Tree

Which node will the next pointer of node $5$ be pointing toward after connecting all the siblings in the given tree?

         _______ 1 _______
        |                  |
     __ 2 _             __ 3__
    |       |          |       |
   _4_    _ 5 _      - 6 -    --7--
  |   |  |     |    |     |  |     |
  8   9  10    11  12    13  14    15

1 / 4

Problem: Connect All Siblings of a Binary Tree

Statement

Examples

Understand the problem

Figure it out!

Try it yourself

Problem: Connect All Siblings of a Binary Tree

Statement

Examples

Understand the problem

Figure it out!

Try it yourself