How do I store level of each node while traversing in BFS?

Question

If we have a binary tree:

      7
    /  \
   5    6
  /\    /\
 2  3   1 4
   /
  5

How can I print the below output?

[7],
[5,6]
[2,3,1,4]
[5]

Means doing a BFS and storing nodes at each level in a list and then printing the list?

I am able to traverse in BFS, but I am not able to find correct level of each element in the tree.

How can I find correct level of each node and enrich the node object with its level value?

This is my logic:

1. Traverse in BFS

2. Enrich each node of the tree with its level value

3. Store node in the list

4. Traverse the list and create a Map of <Level,List<Node>>

5. Store the nodes level in a Set<Integer> and then convert to list and sort it.

6. Iterate through the newly created List of level and find the appropriate node on that list from map and print it

Answer 1

The simplest way is just to do the BFS one level at a time. Instead of putting elements through a queue, you put each level in a list and generate the next level in a new list:

List<Node> level = List.of(root);

while (!level.isEmpty()) {
    System.out.println(level);
    level = level.stream()
                .flatMap(node -> Stream.of(node.left, node.right))
                .filter(Objects::nonNull)
                .collect(Collectors.toList());
}

Note that System.out.println(level) assumes that Node.toString() returns the stringified value. If you don't want to do that then you can map level to a list of integers before printing.

Answer 2

The Tree traversal would be:

7 - 5 - 7 - 6 - 7 - 5 - 2 - 5 - 3 - 5 - 3 - 5 - 7 -6 - 1 - 6 - 4

The logic is.

Always Pick the left child If you can't pick a left child, pick a right child If you can't pick any child, go to the parent

In terms of the printing, keep track of the nodes you have visited and if you have visited them then don't print them, that way you wont print the "back tracking"

Your Node (in pseudo code) should look like:

Node {
   Node *parent;
   Node *child_left;
   Node *child_right;
   Boolean visited;
   int level;
}

Each node should have a parent (except root node), and optionally have children. Once you traverse it set visited to true.

When you go down a level (i.e. visit a child) you should increment a global_level variable. When you go back up (i.e. visit parent) you should decrement it.

In terms of storing them in a list you can just have a global list, just simply don't push it if it already has been visited.

Answer 3

Traverse using BFS.

Have 2 counts - one being the number of nodes remaining in the current level (starting off at 1) and number of nodes remaining on the next level (starting off at 0).

Whenever you process a node, decrease the current level count, and increase the next level count for each child added to the queue.

If the current level count gets to 0, start a new list. Set the current level count to be the next level count and set the current level count to 0.

Your tree as example:

Current level count = 1
Next level count = 0

Queue: 7
Dequeue 7, enqueue 5 and 6.

Current list: [7]

Current level count = 1 - 1 = 0
Next level count = 0 + 2 = 2

Current level count == 0, so
Current level count = Next level count = 2
Next level count = 0

Finished with [7], starting a new list


Queue: 5, 6
Dequeue 5, enqueue 2 and 3.

Current list: [5]

Current level count = 2 - 1 = 1
Next level count = 0 + 2 = 2


Queue: 6, 2, 3
Dequeue 6, enqueue 1 and 4.

Current list: [5, 6]
...

Answer 4

With an assumption that all nodes in the tree will be from 1 to n, we can use two arrays to store the level of the nodes.

int [] parent = new int[n + 1];//To store the direct parent of the current node
int [] level = new int[n + 1];//To store the level of the current node

Starting with level 0 at root , index 7 will have value level[7] = 0; and its two children 5 and 6 will have parent[5] = 7 and parent[6] = 7; similarly, level[5] = level[parent[5]] + 1 and level[6] = level[parent[6]] + 1.

With these steps, you can gradually build up your tree structure by filling in the parent and the level array by BFS.

Pseudo code

int [] parent = new int[n + 1];
int [] level = new int[n + 1];
Queue q = new Queue();
level[root.index] = 0;
q.add(root);
while(!q.isEmpty()){
    Node node = q.dequeue();
    parent[node.left.index] = node.index;
    parent[node.right.index] = node.index;
    level[node.left.index] = level[parent[node.left.index]] + 1;
    level[node.right.index] = level[parent[node.right.index]] + 1;
    q.add(node.left);
    q.add(node.right);

}

Answer 5

Here is a way to do it without making any changes to the tree node structure or any thing else.

1. Keep a levelcounter = 0 of current level while reading the BFS queue

2. Also keep the nextlevel pointer to node which is first in the next level in the queue.

3. Inital nextlevel = null.

4. When new child is added to queue check if nextlevel pointer is not null , if null then set it to current child node pointer.

5. If nextlevel is equal to pointer of recently deleted child then increment levelcounter and set nextlevel = null

The level indicated by levelcounter is your nodes level in tree.

Answer 6

As part of traversing the Tree with BFS and storing the elements in Q. In each level, you can check how many elements are in the Q before adding the next level elements.

Queue<Node> q = new LinkedList<>();
q.offer(head);
while (!q.isEmpty()){
    int levelSize = q.size();
    for (int i=0; i<levelSize; i++){
        Node n = q.poll();
        System.out.print(n.val);
        if (n.left!=null) q.offer(n.left);
        if (n.right!=null) q.offer(n.right);
    }
    System.out.println("");
}