How to keep track of depth in breadth first search?

Actually, we don’t need an extra queue to store the info on the current depth, nor do we need to add null to tell whether it’s the end of current level. We just need to know how many nodes the current level contains, then we can deal with all the nodes in the same level, and increase the level by 1 after we are done processing all the nodes on the current level.

int level = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
    int level_size = queue.size();
    while (level_size-- != 0) {
        Node temp = queue.poll();
        if (temp.right != null) queue.add(temp.right);
        if (temp.left != null) queue.add(temp.left);
    }    
    level++;
}

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)