111. Minimum Depth of Binary Tree

https://leetcode.com/problems/minimum-depth-of-binary-tree/

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:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

---
Intuition

We need to find first leaf node at any level. Level order traversal  => BFS - Queue based.
BFS is right choice and faster for this problem since it exits at first leaf node on first level

DFS is also possible - keep track of depth of each node, and find global minimum depth from all nodes
---
Time - O(n)
Space - O(n)
---

Related problems
104-maximum-depth-of-binary-tree
366-find-leaves-of-binary-tree
---

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public int minDepth(TreeNode root) {
	if (root == null) {
	return 0;
	}
	if (root.left == null) {
	return 1 + minDepth(root.right);
	}
	if (root.right == null) {
	return 1 + minDepth(root.left);
	}
	int lDepth = minDepth(root.left);
	int rDepth = minDepth(root.right);
	return 1 + Math.min(lDepth, rDepth);
	}
	}

view raw 111.MinimumDepthOfBinaryTreeRecursive.java hosted with ❤ by GitHub

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public int minDepth(TreeNode root) {
	if (root == null) {
	return 0;
	}
	Queue<TreeNode> q = new LinkedList<TreeNode>();
	q.offer(root);
	int level = 1;
	while (!q.isEmpty()) {
	int size = q.size();
	for (int i = 0; i < size; i++) {
	TreeNode node = q.poll();
	if (node.left == null && node.right == null) {
	return level;
	}
	if (node.left != null) {
	q.offer(node.left);
	}
	if (node.right != null) {
	q.offer(node.right);
	}
	}
	level++;
	}
	return level;
	}
	}

view raw 111.MinimumDepthOfBinaryTreeBFS.java hosted with ❤ by GitHub

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public class NodeDepth {
	TreeNode node;
	int depth;
	public NodeDepth(TreeNode node, int depth) {
	this.node = node;
	this.depth = depth;
	}
	}
	public int minDepth(TreeNode root) {
	if (root == null) {
	return 0;
	}
	Stack<NodeDepth> stack = new Stack<NodeDepth>();
	stack.push(new NodeDepth(root, 1));
	int ans = Integer.MAX_VALUE;
	while (!stack.isEmpty()) {
	NodeDepth nd = stack.pop();
	TreeNode node = nd.node;
	if (node.left != null) {
	stack.push(new NodeDepth(node.left, nd.depth + 1));
	}
	if (node.right != null) {
	stack.push(new NodeDepth(node.right, nd.depth + 1));
	}
	if (node.left == null && node.right == null) {
	ans = Math.min(ans, nd.depth);
	}
	}
	return ans;
	}
	}

view raw 111.MinimumDepthOfBinaryTreeDFS.java hosted with ❤ by GitHub