Minimum Depth of Binary Tree🛩

Question

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

Java Solution

Two different solutions with same time complexity but one is using Breadth-first search technique to traverse the tree level by level and the other one is using pre-order traverse i.e. node->left->right

Time Complexity of below solutions
O(n), in the pre-order traversal we are visiting each node only once and in the case of breadth-first search it may seem first it's not O(n) because of the inner loop but it is O(n).
Here is the explanation, the outer loop will run O(log n) i.e. the number of levels a tree has and the inner loop will run O(n), and since as it’s the rule of big O to drop non dominate terms that’s why O(n).
In reality, Breadth-first search is more efficient than the first one since its checks the tree level by level and as soon as it detects the node with no childrens it stops the execution.

Code

Pre-Order

BTF