# BFS with nesting calculation

• Assume root has nesting 0. For each node except root , it's nesting will be parent's nesting - 1 if it's a left child and parent's nesting + 1 if it's right child.

Run a BFS to traverse the nodes level wise.

• For each node, calculate it's nesting.
• For each nesting, maintain a list of node values having the same nesting. Calculate min and max nesting also.

Iterate from min nesting to max nesting and collect all the lists associated with each nesting.

``````private static class NodeNesting {
private final TreeNode node;
private final int nesting;

public NodeNesting(final TreeNode node, final int nesting) {
this.node = node;
this.nesting = nesting;
}
}

public List<List<Integer>> verticalOrder(final TreeNode root) {
if (root == null) {
return Collections.emptyList();
}

Map<Integer, List<Integer>> nestingValueMap = new HashMap<>();
int minNesting = Integer.MAX_VALUE, maxNesting = Integer.MIN_VALUE;

queue.offer(new NodeNesting(root, 0));

while (!queue.isEmpty()) {
int totalCurrentLevel = queue.size();

for (int i = 0; i < totalCurrentLevel; i++) {
NodeNesting current = queue.poll();
TreeNode node = current.node;
int nesting = current.nesting;

List<Integer> values = nestingValueMap.getOrDefault(nesting, new ArrayList<>());
nestingValueMap.put(nesting, values);

minNesting = Math.min(minNesting, nesting);
maxNesting = Math.max(maxNesting, nesting);

if (node.left != null) {
queue.offer(new NodeNesting(node.left, nesting-1));
}

if (node.right != null) {
queue.offer(new NodeNesting(node.right, nesting+1));
}
}
}

List<List<Integer>> result = new ArrayList<>();
for (int nesting = minNesting; nesting <= maxNesting; nesting++) {