An algorithm for navigating or searching over tree or graph data structures is called breadth-first search (BFS). It begins at the root of the tree (or any other random node in a graph; this is frequently referred to as the “search key”) and initially looks at its neighbors before going on to its next-level neighbors.
The following graph shows the order in which the nodes are discovered in BFS:
A graph traversal algorithm called breadth-first search (BFS) investigates vertices in the order of their distance from the source vertex, where distance is the shortest distance between the source vertex and the node, as is seen from the example above.
// using BFS
// in this method, we just have to count levels of tree that will become its height.
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL)
return 0;
int level = 0;
queue <TreeNode*> q;
q.push(root);
while(!q.empty()){
int currLength = q.size();
level++;
//Iterate till the current length of Queue
for(int i=0; i<currLength; i++){
TreeNode* curr = q.front();
q.pop();
if(curr -> left)
q.push(curr -> left);
if(curr -> right)
q.push(curr -> right);
// If Both left and right nodes are null, means we reached minimum height
// at that time time level i.e. height
if(curr -> left == NULL && curr -> right == NULL){
return level;
}
}
}
return level;
}
};
All credits goes to Harcharan Preet Singh
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6] Output: 5
Constraints:
- The number of nodes in the tree is in the range
[0, 105]. -1000 <= Node.val <= 1000
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
}
};