Level Order Successor (Next Node in BFS Order)

Perform a plain Tree BFS without tracking level boundaries, enqueuing children as usual. When the dequeued node equals the target, the very next node still in the queue (the next to be dequeued) is its level order successor. Return that node, or null if the queue is then empty.

What is the problem?

Level Order Successor (Next Node in BFS Order). Given the root of a binary tree and the value of a target node, find its level order successor, the node that appears immediately after the target in a breadth-first traversal. Return null if the target is the last node.

How does the approach work?

Because the successor is defined across the entire BFS order (it may be the first node of the next level), you do not need the level-size snapshot here. Enqueue the root, then loop: dequeue a node, enqueue its children, and if the node you just dequeued is the target, break out; the next queue.poll() (or queue.peek()) is the successor. If the queue is empty after the target, there is no successor.

For example in a tree whose BFS order is 1,2,3,4,5, the successor of 3 is 4, and the successor of 5 is null. A clean way: after dequeuing and enqueuing children, check if (node.id == target) break; then return the queue's head.

A senior-level nuance is that children must be enqueued before the break check, so that when the target is the last node of its level, its children (the next level's start) are already in the queue and the successor is found correctly. Forgetting to enqueue first produces a wrong null at level boundaries, a subtle but common error.

What is the banking use case?

The code contains a RouteNode, a SuccessorRouter with levelOrderSuccessor(root, target), and a demo.

How do you implement this in Java?

// ─── File: src/main/java/com/bank/successor/RouteNode.java ───
package com.bank.successor;

public class RouteNode {
    final int id;
    RouteNode left, right;
    RouteNode(int id) { this.id = id; }
}

// ─── File: src/main/java/com/bank/successor/SuccessorRouter.java ───
package com.bank.successor;

import java.util.*;

public class SuccessorRouter {

    public RouteNode levelOrderSuccessor(RouteNode root, int target) {
        if (root == null) return null;
        Queue<RouteNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            RouteNode node = queue.poll();
            // Enqueue children FIRST so the next-level start is present at a boundary.
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (node.id == target) break;      // found target; successor is queue head
        }
        return queue.peek();                    // next to be dequeued, or null
    }
}

// ─── File: src/main/java/com/bank/successor/SuccessorDemo.java ───
package com.bank.successor;

import java.util.logging.Logger;

public class SuccessorDemo {
    private static final Logger log = Logger.getLogger(SuccessorDemo.class.getName());

    public static void main(String[] args) {
        // BFS order: 1,2,3,4,5
        RouteNode root = new RouteNode(1);
        root.left = new RouteNode(2);
        root.right = new RouteNode(3);
        root.left.left = new RouteNode(4);
        root.left.right = new RouteNode(5);

        RouteNode succ = new SuccessorRouter().levelOrderSuccessor(root, 3);
        log.info("Successor of 3: " + (succ == null ? "none" : succ.id));
    }
}

What is the project structure?

successor-router/
├── pom.xml
└── src/main/java/com/bank/successor/
    ├── SuccessorDemo.java
    ├── RouteNode.java
    └── SuccessorRouter.java

How do you build and run?

# Build
mvn clean package -DskipTests
# Run
java -cp target/classes com.bank.successor.SuccessorDemo

What is the step-by-step walkthrough?

Input data: tree with BFS order 1,2,3,4,5; target 3.

Final output:

2026-10-27 19:25:42 [INFO] Successor of 3: 4

What is the high-level design?

  ═══ HLD — Approver Fallback Routing ═══

  ┌──────────┐ reroute ┌────────────────────┐ tree ┌──────────────┐
  │ Workflow │────────→│ Successor Svc ×2   │─────→│ approval tree│
  └──────────┘         │ levelOrderSuccessor│      └──────────────┘
                       └────────────────────┘

What is the low-level design?

  ═══ LLD — SuccessorRouter ═══

  ┌─ Critical ordering ─────────────────────────────────┐
  │  enqueue children BEFORE the target-match break      │
  │  → correct successor across level boundary           │
  └──────────────────────────────────────────────────────┘

  ┌──────────────────────────────────────────────┐
  │               SuccessorRouter                 │
  │  + levelOrderSuccessor(root,target):RouteNode │  O(n), O(w)
  └──────────────────────────────────────────────┘

  Contract for levelOrderSuccessor(root,target):
    Pre:  target exists in the tree
    Post: returns next node in BFS order, or null if target is last

What is the time and space complexity?

Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.

What are common mistakes?

Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.

What are the edge cases?

Edge cases include empty input, single element input, all identical elements, and boundary values.

What should a senior engineer know?

A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.