Check if the given permutation is a valid BFS of a given tree

Ishita Chawla
Last Updated: May 13, 2022

Introduction

Breadth-First Search(or BFS) is an essential level-based graph traversing algorithm that can be used to solve several problems based on the simple concepts of graphs. These include finding the shortest path in a graph and solving puzzle games like Rubik's Cubes.

This blog will discuss one such problem that will utilize this concept of BFS. Let us first understand the problem before jumping onto the solution.

Problem Statement

You have been given a tree having N nodes, being numbered from 1 to N. You have also been given a permutation array, i.e., an array containing all elements from 1 to N in a specific order. Your task is to check if this given permutation can be obtained by performing BFS traversal on the given tree. 

Also, note that the traversal will always start from 1.

Let's look at an easy example to gain a clear picture of the problem:

Example

  • Edges of the tree given:
    • 1 - 2
    • 2 - 3

     A = {1, 2, 3}

 The given permutation is a valid BFS of the tree that has been given.

Approach

  • One thing that needs to be kept in mind is that while performing BFS traversal on a tree, all the neighbors of the current node are visited and their children are pushed into the queue in an ordered manner. This process is repeated until the queue becomes empty.
  • Assume that root has two children, A and B. We have the option of visiting any of them first. Let's say we go to A first, but now we'll have to push the children of A to the front of the queue, and we won't be able to visit the children of B before A.
  • So, although we can visit the children of one node in any order, the order in which the children of two different nodes should be visited is fixed, i.e., if A is visited before B, then all of A's children should be visited before all of B's children.


We will use this concept to solve the problem given here.

Algorithm

  • We will start with an empty queue of sets.
  • In each set, we'll push the children of a specific node while traversing the permutation.
  • We will proceed if the current element of the permutation is found in the set at the top of the queue; else, we will return false.

Implementation

Program

// C++ program to check if the given permutation is a valid BFS of a given tree.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;

// Function to check if the given permutation is a valid BFS of a given tree.
bool isValidBFS(vector<int> & bfs, unordered_map<int, vector<int>> & tree)
{
    // If the first element of 'BFS' is not present in the tree, return false.
    if (tree.count(bfs[0]) == 0) {
        return false;
    }

    // Number of nodes in the tree.
    int n = bfs.size();

    // 'VISITED' hash set to keep track of visited nodes.
    unordered_set<int> visited;

    // 'LEVEL' hash set to keep track of nodes at each level.
    unordered_set<int> level;

    // Inserting root node.
    level.insert(bfs[0]);

    // Queue for BFS traversal.
    queue<unordered_set<int>> q;

    // Inserting the root level in front of the queue.
    q.push(level);

    // Variable to iterate over 'BFS' array.
    int i = 0;

    while (!q.empty() && i < n)
    {
        // In case the current node has already been visited, return false.
        if (visited.count(bfs[i]))
        {
            return false;
        }

        visited.insert(bfs[i]);

        // If all the child nodes of the previous nodes have been visited, then pop the front element of the queue.
        if (q.front().empty())
        {
            q.pop();
        }

        // Return false, if the current element of the permutation cannot be found in the set at the top of the queue.
        level = q.front();      
        if (level.count(bfs[i]) == 0)
        {
            return false;
        }
        level.clear();

        // All the children of the current node are pushed into the 'LEVEL' hashset and then this hashset is pushed into the queue.
        for (int &j : tree[bfs[i]])
        {
            if (!visited.count(j))
            {
                level.insert(j);
            }
        }
        if (level.empty() == false)
        {
            q.push(level);
        }

        // The current node is erased from the set at the top of the queue.
        q.front().erase(bfs[i]);

        // The index of permutation is incremented.
        i++;
    }

    return true;
}
int main()
{
    // Given adjacency list representation of tree.
    unordered_map<int, vector<int>> tree;
    tree[3].push_back(7);
    tree[7].push_back(3);
    tree[3].push_back(2);
    tree[2].push_back(3);
    tree[2].push_back(8);
    tree[8].push_back(2);
    tree[2].push_back(13);
    tree[13].push_back(2);
    tree[8].push_back(14);
    tree[14].push_back(8);
    tree[13].push_back(4);
    tree[4].push_back(13);

    // BFS permutation.
    vector<int> bfs = {3, 2, 7, 13, 8, 14, 4};

    // Calling the function and checking whether the given permutation is a valid BFS of a given tree.
    if (isValidBFS(bfs, tree))
        cout << "Yes, the given permutation is a valid BFS of a given tree." << endl;

    else
        cout << "No, the given permutation is not a valid BFS of a given tree." << endl;

    return 0;
}

Output

No, the given permutation is not a valid BFS of a given tree. 

Time Complexity

The time complexity is O(N), where N is the total number of nodes in the given tree. 

We are traversing all the N nodes using a while loop, and at every step, we are doing the constant amount of work, therefore, the time complexity is O(1 * N) = O(N).

Space Complexity

The space complexity is O(N), where N is the total number of nodes in the given tree. 

Extra space in the form of HashSet, hashmap, and the queue is being used which consumes a space of O(N).

Key Takeaways

So, this blog discussed the problem, check if the given permutation is a valid BFS of a given tree. Head over to CodeStudio to practice problems on topics like Graphs, and Trees and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

Feel free to post any suggestions in the comments section.

Was this article helpful ?
0 upvotes