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 to the solution.

Problem Statement

We are given a tree with N nodes, numbered from 1 to N. We have also been given a permutation array, i.e., an array containing all elements from 1 to N in a specific order. Our 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:

Sample Example

Input

N=6,

Permutation Array => arr[] = {1, 3, 2, 6, 5, 4}

Output

The given permutation is a valid BFS of the tree. The BFS of the given tree is:

1 â€“> 3 â€“> 2 â€“> 6 â€“> 5 â€“> 4

Approach

In this approach, we will perform BFS traversal on the tree, neighbors of the current node will be visited, and their children will be pushed into the queue. We will repeat this process until the queue becomes empty.

Let us assume that a node has two children, 1 and 2. We can visit either of them first. Suppose we visit 1 first, now we'll push the children of 1 to the front of the queue, and we canâ€™t visit the children of 2 before the children of 1.

So, the thing is, we can visit the children of one node in any order, but the order in which the children of two different nodes should be visited is fixed, i.e., if 1 is visited before 2, then all of 1's children should be visited before all of 2â€™s children.

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

Algorithm

We will start with an empty queue of unordered_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.

Dry Run

Step-1

In the first step, only the root node will be visited and only present in the queue.

After visiting the root node, the index of the permutation array will be incremented. The children of the root node will be inserted in an unordered set, and the set will be pushed inside the queue.

Step-2

In the second step, we will check if the current element of the permutations array, i.e., 3 (i=1), is present in the queue or not, and since it is present in the queue, it will be marked as visited, we will pop it from the queue, and we will insert an unordered_set (which will contain the children) inside the queue.

Step-3

In step-3 the index value will be 2, and thus we will check if the 2 is present in the queue, and since it is present, it will be marked as visited, popped from the queue, and we will also insert its children (i.e., 4 only) inside a set and that set will be pushed in the queue.

Step-4

Now, the i value will be 3, and we will repeat the same steps for 6 also. We will mark it visited, and simultaneously, we will insert its children (none) in the set and pop it from the queue. (index will be incremented)

Step-5

In this step, the above process will be repeated for 5.

Step-6

Lastly, the process described in the above steps will also be repeated for the 4, the last element of the permutations array.

Implementation in C++

// 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, vector<int> *tree)
{
// If the first element of 'BFS' is not present in the tree, return false.
if (tree[bfs[0]].size() == 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())
{
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()
{
int n = 6;
// Given adjacency list representation of tree.
vector<int> tree[n + 1];
tree[1].push_back(2);
tree[1].push_back(3);
tree[3].push_back(6);
tree[3].push_back(5);
tree[2].push_back(4);
// BFS permutation.
vector<int> bfs = {1, 3, 2, 6, 5, 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;
}

You can also try this code with Online C++ Compiler

Yes, the given permutation is a valid BFS of a given tree.

Complexities

Time Complexity

The time complexity is O(Nlog(N)), where N is the 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 a log(N) amount of work; therefore, the time complexity is O(Nlog(N).

Space Complexity

The space complexity is O(N), where N is the 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).

Frequently Asked Questions

What is BFS traversal in a binary tree?

BFS (breadth-first search) is a traversal technique that explores all the nodes at the current level before moving to the next level. In a binary tree, BFS traversal starts at the root node and visits all the nodes in the tree level by level, from left to right.

What is the time complexity of BFS traversal in a binary tree?

The time complexity of BFS traversal in a binary tree is O(n), where n is the number of nodes in the tree. This is because BFS visits every node in the tree exactly once.

What are permutations?

Permutations are all the possible arrangements of a set of elements. For example, the permutations of the set {1, 2, 3} are {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}.

How many permutations are there for a set of n elements?

The number of permutations for a set of n elements is n! which is the product of all positive integers up to n.

How is BFS traversal implemented in a binary tree?

BFS traversal in a binary tree is usually implemented using a queue data structure. The algorithm works by inserting the root node into the queue, then repeatedly dequeuing a node from the front of the queue, visiting it, and then enqueueing its children at the back of the queue.

Conclusion

So, this blog discussed the problem, check if the given permutation is a valid BFS of a given tree. Head over to Coding Ninjas Studio 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 check out where you stand among your peers by taking our mock tests and see which areas need improvement.