How to keep track of depth in breadth first search

Question

I have a tree as input to the breadth first search and I want to know as the algorithm progresses at which level it is?

# Breadth First Search Implementation
graph = { 
    'A':['B','C','D'],
    'B':['A'],
    'C':['A','E','F'],
    'D':['A','G','H'],
    'E':['C'],
    'F':['C'],
    'G':['D'],
    'H':['D']
    }


def breadth_first_search(graph,source):
    """
    This function is the Implementation of the breadth_first_search program
    """
    # Mark each node as not visited
    mark = {}
    for item in graph.keys():
        mark[item] = 0

    queue, output = [],[]

    # Initialize an empty queue with the source node and mark it as explored
    queue.append(source)
    mark[source] = 1
    output.append(source)

    # while queue is not empty
    while queue:
        # remove the first element of the queue and call it vertex
        vertex = queue[0]
        queue.pop(0)
        # for each edge from the vertex do the following
        for vrtx in graph[vertex]:
            # If the vertex is unexplored
            if mark[vrtx] == 0:
                queue.append(vrtx)  # mark it as explored
                mark[vrtx] = 1      # and append it to the queue
                output.append(vrtx) # fill the output vector
    return output

print breadth_first_search(graph, 'A')

It takes tree as an input graph, what I want is, that at each iteration it should print out the current level which is being processed.

Answer 1

With this Python code you can maintain the depth of each node from the root by increasing the depth only after you encounter a node of new depth in the queue.

    queue = deque()
    marked = set()
    marked.add(root)
    queue.append((root,0))

    depth = 0
    while queue:
        r,d = queue.popleft()
        if d > depth: # increase depth only when you encounter the first node in the next depth               
            depth += 1
        for node in edges[r]:
            if node not in marked:
                marked.add(node)
                queue.append((node,depth+1))

Answer 2

You don't need to use extra queue or do any complicated calculation to achieve what you want to do. This idea is very simple.

This does not use any extra space other than queue used for BFS.

The idea I am going to use is to add null at the end of each level. So the number of nulls you encountered +1 is the depth you are at. (of course after termination it is just level).

     int level = 0;
     Queue <Node> queue = new LinkedList<>();
     queue.add(root);
     queue.add(null);
     while(!queue.isEmpty()){
          Node temp = queue.poll();
          if(temp == null){
              level++;
              queue.add(null);
              if(queue.peek() == null) break;// You are encountering two consecutive `nulls` means, you visited all the nodes.
              else continue;
          }
          if(temp.right != null)
              queue.add(temp.right);
          if(temp.left != null)
              queue.add(temp.left);
     }

Answer 3

Try having a look at this post. It keeps track of the depth using the variable currentDepth

https://stackoverflow.com/a/16923440/3114945

For your implementation, keep track of the left most node and a variable for the depth. Whenever the left most node is popped from the queue, you know you hit a new level and you increment the depth.

So, your root is the leftMostNode at level 0. Then the left most child is the leftMostNode. As soon as you hit it, it becomes level 1. The left most child of this node is the next leftMostNode and so on.

Answer 4

If your tree is perfectly ballanced (i.e. each node has the same number of children) there's actually a simple, elegant solution here with O(1) time complexity and O(1) space complexity. The main usecase where I find this helpful is in traversing a binary tree, though it's trivially adaptable to other tree sizes.

The key thing to realize here is that each level of a binary tree contains exactly double the quantity of nodes compared to the previous level. This allows us to calculate the total number of nodes in any tree given the tree's depth. For instance, consider the following tree:

This tree has a depth of 3 and 7 total nodes. We don't need to count the number of nodes to figure this out though. We can compute this in O(1) time with the formaula: 2^d - 1 = N, where d is the depth and N is the total number of nodes. (In a ternary tree this is 3^d - 1 = N, and in a tree where each node has K children this is K^d - 1 = N). So in this case, 2^3 - 1 = 7.

To keep track of depth while conducting a breadth first search, we simply need to reverse this calculation. Whereas the above formula allows us to solve for N given d, we actually want to solve for d given N. For instance, say we're evaluating the 5th node. To figure out what depth the 5th node is on, we take the following equation: 2^d - 1 = 5, and then simply solve for d, which is basic algebra:

If d turns out to be anything other than a whole number, just round up (the last node in a row is always a whole number). With that all in mind, I propose the following algorithm to identify the depth of any given node in a binary tree during breadth first traversal:

1. Let the variable visited equal 0.
2. Each time a node is visited, increment visited by 1.
3. Each time visited is incremented, calculate the node's depth as depth = round_up(log2(visited + 1))

You can also use a hash table to map each node to its depth level, though this does increase the space complexity to O(n). Here's a PHP implementation of this algorithm:

<?php
$tree = [
    ['A', [1,2]],
    ['B', [3,4]],
    ['C', [5,6]],
    ['D', [7,8]],
    ['E', [9,10]],
    ['F', [11,12]],
    ['G', [13,14]],
    ['H', []],
    ['I', []],
    ['J', []],
    ['K', []],
    ['L', []],
    ['M', []],
    ['N', []],
    ['O', []],
];

function bfs($tree) {
    $queue = new SplQueue();
    $queue->enqueue($tree[0]);
    $visited = 0;
    $depth = 0;
    $result = [];

    while ($queue->count()) {

        $visited++;
        $node = $queue->dequeue();
        $depth = ceil(log($visited+1, 2));
        $result[$depth][] = $node[0];


        if (!empty($node[1])) {
            foreach ($node[1] as $child) {
                $queue->enqueue($tree[$child]);
            }
        }
    }
    print_r($result);
}

bfs($tree);

Which prints:

    Array
    (
        [1] => Array
            (
                [0] => A
            )

        [2] => Array
            (
                [0] => B
                [1] => C
            )

        [3] => Array
            (
                [0] => D
                [1] => E
                [2] => F
                [3] => G
            )

        [4] => Array
            (
                [0] => H
                [1] => I
                [2] => J
                [3] => K
                [4] => L
                [5] => M
                [6] => N
                [7] => O
            )

    )

Answer 5

Maintain a queue storing the depth of the corresponding node in BFS queue. Sample code for your information:

queue bfsQueue, depthQueue;
bfsQueue.push(firstNode);
depthQueue.push(0);
while (!bfsQueue.empty()) {
    f = bfsQueue.front();
    depth = depthQueue.front();
    bfsQueue.pop(), depthQueue.pop();
    for (every node adjacent to f) {
        bfsQueue.push(node), depthQueue.push(depth+1);
    } 
}

This method is simple and naive, for O(1) extra space you may need the answer post by @stolen_leaves.