In this post we will solve LeetCode 111. Minimum Depth of Binary Tree problem using Java and the VSCode IDE on a Windows computer. Not that it matters, but I am using Windows 11.
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. Constraints: o The number of nodes in the tree is in the range [0, 10^5]. o -1000 <= Node.val <= 1000 Related Topics: o Tree * Depth-First Search * Breadth-First Search o Binary Tree
We are given the root of a binary tree and are asked to find the minimum depth of the tree. A couple years ago we solved in this post Maximum Depth of a Binary Tree.
The definition of minimum depth is provided in the requirements for the problem at hand.
What called my attention to the problem was a comment that I read regarding the Minimum Depth of Binary Tree. It gave the impression that LeetCode had an issue with the solution on their site. It turned out that the author was calling attention to a YouTube video.
My approach was to read the problem at LeetCode, solve it and then watch the video to find out what the problem was about. I guess I fell for it. There was no problem.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
}
}
Since we are going to solve the problem in Java, we need to use the signature for the function of interest. We are just given the root of a binary tree and we need to return the minimum depth.
LeetCode provides us with a description of the TreeNode class which is used to generate the nodes in the binary tree.
Since I will be solving the problem on my computer, I will need to develop a simple (perhaps not that simple) test scaffold which will read the input data for the binary tree, generate the tree, call the function of interest and display the result.
3,9,20,null,null,15,7 main <<< strArr: [3, 9, 20, null, null, 15, 7] main <<< arr: [3, 9, 20, null, null, 15, 7] main <<< inOrder: 9 3 15 20 7 main <<< postOrder: 9 15 7 20 3 main <<< levelOrder: 3 9,20 15,7 main <<< maxDepth: 3 main <<< minDepth: 2 2,null,3,null,4,null,5,null,6 main <<< strArr: [2, null, 3, null, 4, null, 5, null, 6] main <<< arr: [2, null, 3, null, 4, null, 5, null, 6] main <<< inOrder: 2 3 4 5 6 main <<< postOrder: 6 5 4 3 2 main <<< levelOrder: 2 3 4 5 6 main <<< maxDepth: 5 main <<< minDepth: 5 0 main <<< strArr: [0] main <<< arr: [0] main <<< inOrder: 0 main <<< postOrder: 0 main <<< levelOrder: 0 main <<< maxDepth: 1 main <<< minDepth: 1
Each test case is separated from others by two blank lines.
The first and only input line holds the values for the nodes in a depth first search mode.
Our test scaffold seems to read the input line into a String[] array. With that data a Integer[] array `arr` is populated. That array is then used to build the binary tree.
Once the binary tree has been populated, we seem to perform an in-order, a post-order, and a level-order traversal. This is done to make sure all is well and to provide us some insights as to how we could approach a solution.
In addition, it seems we compute the maximum depth of the binary tree before we call the function of interest and display the minimum depth of the tree.
Please note that the test scaffold IS NOT PART OF THE SOLUTION. The simplest approach is to use the on-line IDE provided by LeetCode.
/**
* Test scaffold.
* !!!! NOT PART OF THE SOLUTION !!!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and populate string[] for binary tree ****
String[] strArr = br.readLine().trim().split(",");
// ***** close the buffered reader ****
br.close();
// ????? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** generate Integer[] to create and populate binary tree ****
int len = strArr.length;
Integer[] arr = new Integer[len];
for (int i = 0; i < len; i++)
arr[i] = strArr[i].equals("null") ? null : Integer.parseInt(strArr[i]);
// ????? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** create and populate per level the binary tree ****
BST bt = new BST();
bt.root = bt.populate(arr);
// ???? in-order traversal ????
System.out.println("main <<< inOrder: " + bt.inOrder());
// ???? post-order traversal ????
System.out.println("main <<< postOrder: " + bt.postOrder());
// ???? level-order traversal ????
System.out.println("main <<< levelOrder: " + bt.levelOrder());
// ???? ????
System.out.println("main <<< maxDepth: " + bt.maxDepth(bt.root));
// **** call the function of interest and display result ****
System.out.println("main <<< minDepth: " + minDepth(bt.root));
}
I am not going to add much to the description of the test scaffold code. Based on the description of a test case, you should be able to get a good understanding of what is going on.
/**
* Given a binary tree, find its minimum depth.
* Entry point for recursive calls.
*
* Runtime: 6 ms, faster than 53.62% of Java online submissions.
* Memory Usage: 62.3 MB, less than 62.12% of Java online submissions.
*
* 52 / 52 test cases passed.
* Status: Accepted
* Runtime: 6 ms
* Memory Usage: 62.3 MB
*
* Execution: O(log(n)) or O(n) - Space: O(1)
*/
static public int minDepth(TreeNode root) {
// **** sanity check(s) ****
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
// **** initialization ****
var leftDepth = Integer.MAX_VALUE;
var rightDepth = Integer.MAX_VALUE;
// **** traverse left - O(log(n)) ****
if (root.left != null)
leftDepth = minDepth(root.left, 1);
// **** traverse right - O(log(n)) ****
if (root.right != null)
rightDepth = minDepth(root.right, 1);
// **** return min depth ****
// return Math.min(leftDepth, rightDepth);
return leftDepth >= rightDepth ? rightDepth : leftDepth;
}
This function is the entry point for a recursive method we will see shortly.
We start by performing a couple sanity checks.
The `leftDepth` is used to get the depth of the left child of the root of the binary tree. The `rightDepth` is for the left child of the binary tree.
Each time we call the `minDepth` recursive call, we increase the depth by one. In general the depth of the root node is considered to be at level 1.
/**
* Recursive call.
*
* Execution: O(log(n)) or O(n) - Space: O(1)
*/
static private int minDepth(TreeNode root, int depth) {
// **** base case ****
if (root.left == null && root.right == null)
return depth + 1;
// **** initialization ****
var leftDepth = Integer.MAX_VALUE;
var rightDepth = Integer.MAX_VALUE;
// **** traverse left - O(log(n)) ***
if (root.left != null)
leftDepth = minDepth(root.left, depth + 1);
// **** traverse right - O(log(n)) ****
if (root.right != null)
rightDepth = minDepth(root.right, depth + 1);
// **** return min depth ****
// return Math.min(leftDepth, rightDepth);
return leftDepth >= rightDepth ? rightDepth : leftDepth;
}
The recursive call starts with the base case in which we increment the depth by one and return it to the caller.
We initialize a couple variables that are used to track the depths of the two child nodes.
The recursive calls are made and the minimum value is returned.
Please take a look at the comment section for the entry point function. It contains performance information.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named MinimumDepthOfBinaryTree.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John