Definition
- Level-size snapshot – isolate each level using the standard BFS snapshot.
- Previous pointer – track the previously dequeued node within each level; set
previous.next = current. - Per-level reset – reset
previousto null at the start of each level so levels are independent. - Last node – the last node of each level naturally keeps
next = nullbecause nothing follows. - Complexity – O(n) time, O(w) space for the queue.
In the National Bank of India approval tree, every approver on a rank should know who sits to their immediate right on the same rank. A stalled request can then slide sideways to the next available approver. You walk each rank left to right and clip each approver's next pointer to the one that follows.
Understanding the Concepts
What is the Connect Level Order Siblings problem?
You are given a binary tree where each node has an extra next pointer (initially null). Connect each node to its immediate right neighbor on the same level. The last node on each level should have next pointing to null. After the operation, each level forms a singly linked list via the next pointers.
How does the BFS solution work?
Use the standard level-size snapshot. Within each level, maintain a previous pointer that starts as null. For each dequeued node, if previous is not null, set previous.next = node. Then update previous = node. At the end of the level, the last node's next stays null.
package com.bank.service;
import java.util.*;
public class SiblingConnector {
static class TreeNode {
int approverRank;
TreeNode left, right, next;
TreeNode(int val) { this.approverRank = val; }
}
public static void connectSiblings(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
TreeNode previous = null;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (previous != null) {
previous.next = node;
}
previous = node;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
// previous.next stays null (last node of level)
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(7);
connectSiblings(root);
// Print next pointers
System.out.println("1.next = " + (root.next == null ? "null" : root.next.approverRank));
System.out.println("2.next = " + root.left.next.approverRank);
System.out.println("3.next = " + (root.right.next == null ? "null" : root.right.next.approverRank));
System.out.println("4.next = " + root.left.left.next.approverRank);
System.out.println("5.next = " + root.left.right.next.approverRank);
System.out.println("7.next = " + (root.right.right.next == null ? "null" : root.right.right.next.approverRank));
}
}
1.next = null
2.next = 3
3.next = null
4.next = 5
5.next = 7
7.next = null
How does the O(1) space solution work for perfect binary trees?
For a perfect binary tree, the next pointers already built on the current level can be used to traverse and wire the next level without a queue.
public static void connectPerfectTree(TreeNode root) {
TreeNode levelStart = root;
while (levelStart != null && levelStart.left != null) {
TreeNode current = levelStart;
while (current != null) {
current.left.next = current.right;
if (current.next != null) {
current.right.next = current.next.left;
}
current = current.next;
}
levelStart = levelStart.left;
}
}
// Time: O(n), Space: O(1) -- no queue needed
How is per-level connect different from connect-all?
| Aspect | Connect Level Siblings | Connect All Level Siblings |
|---|---|---|
| Level boundaries | Each level ends with null | No level breaks; one continuous chain |
| Previous pointer | Reset per level | Never reset |
| Last node of level | next = null | next = first node of next level |
| Use case | Same-rank navigation | Full BFS-order sweep |
The only code difference is whether previous is reset to null at each level's start.
What are the edge cases?
- Null root – do nothing.
- Single node – next stays null (no siblings).
- Left-skewed tree – each level has one node; all next pointers are null.
- Perfect binary tree – all levels fully connected; O(1) space solution applies.
// Edge case: single node
TreeNode single = new TreeNode(42);
connectSiblings(single);
System.out.println(single.next == null); // true
What are common mistakes?
The most common mistake is forgetting to reset previous at each level, which creates cross-level connections.
// WRONG: previous not reset per level
TreeNode previous = null; // outside the while loop
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (previous != null) previous.next = node;
previous = node;
}
}
// This connects the last node of level k to the first node of level k+1
// That's connect-all, not connect-siblings!
// CORRECT: reset previous per level
while (!queue.isEmpty()) {
int levelSize = queue.size();
TreeNode previous = null; // inside the while loop
for (...) { ... }
}
What is the time and space complexity?
The queue-based solution is O(n) time and O(w) space. The O(1) space solution for perfect binary trees uses the next pointers themselves to traverse, eliminating the queue entirely. For a general tree, the queue-based approach is the robust, correct choice.
What should a senior engineer know?
A senior engineer should know both solutions: the queue-based O(w) solution for general trees and the O(1) space solution using next pointers for perfect trees. The O(1) approach cannot handle general trees because a left child's sibling might be a distant cousin reachable only via the parent's next pointer chain.
They should also know that connecting siblings enables efficient same-level traversal without going back to the root, which is useful for level-based queries and horizontal routing in tree-based systems.
Visual Overview
Before: After:
1 1 -> null
/ \ / \
2 3 2 -> 3 -> null
/ \ \ / \ \
4 5 7 4->5 -> 7 -> null
BFS Level-by-Level Wiring:
┌──────────────────────────────────────┐
│ Level 0: [1] │
│ prev=null -> prev=1 │
│ 1.next stays null │
├──────────────────────────────────────┤
│ Level 1: [2, 3] │
│ prev=null -> prev=2 │
│ prev=2 -> 2.next=3, prev=3 │
│ 3.next stays null │
├──────────────────────────────────────┤
│ Level 2: [4, 5, 7] │
│ prev=null -> prev=4 │
│ prev=4 -> 4.next=5, prev=5 │
│ prev=5 -> 5.next=7, prev=7 │
│ 7.next stays null │
└──────────────────────────────────────┘
O(1) Space (Perfect Tree):
Use current level's next pointers to wire next level
current.left.next = current.right
current.right.next = current.next.left
Key Takeaway
Connect Level Order Siblings wires each node's next pointer to its immediate right neighbor on the same level, with the last node of each level pointing to null. The solution uses standard BFS with the level-size snapshot. Within each level, a previous pointer tracks the last dequeued node, and for each new node you set previous.next = node.
The critical detail is resetting previous to null at the start of each level. Without this reset, you create cross-level connections, which is the connect-all variant, not connect-siblings. The last node's next naturally stays null because nothing follows it.
At the National Bank of India, connecting siblings enabled horizontal routing across each rank of the approval tree. A stalled request could be passed to the approver immediately to the right on the same rank instead of escalating to a parent. This sideways navigation was built by the next-pointer wiring.
The senior follow-up is the O(1) space solution for perfect binary trees, which uses the next pointers already established on the current level to traverse and wire the next level without a queue. For general trees, the queue-based approach is the reliable, obviously correct choice.
Remember one sentence: BFS per level with a previous pointer wires each level into a singly linked list; reset previous per level for siblings, or keep it persistent for connect-all.
---