Minimum Depth of Binary Tree

Introduction

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.

Input: root = [3,9,20,null,null,15,7]
Output: 2

TreeNode represents a tree node.

class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int x) {
    val = x;
    left = null;
    right = null;
  }
}

The code is a C# function that returns the minimum depth of a binary tree. The depth of a tree is the number of nodes along the longest path from the root node to the farthest leaf node. The minimum depth is the shortest such path. The function uses recursion to traverse the tree and find the minimum depth. 

public int MinDepth(TreeNode root) {
  if (root == null)
    return 0;
  if (root.left == null && root.right == null)
    return 1;
  if (root.left == null)
    return MinDepth(root.right) + 1;
  if (root.right == null)
    return MinDepth(root.left) + 1;

  return Math.Min(MinDepth(root.left), MinDepth(root.right)) + 1;

}

1. Checking if the root is null. If so, it means the tree is empty, so it returns 0 as the minimum depth.
2. Check if the root has no children (left and right are null). If so, the tree has only one node, so it returns 1 as the minimum depth.
3. Checking if the root has only one child (either left or right is null). If so, it means the minimum depth is determined by the subtree that has the child, so it recursively calls itself with that subtree as the argument and adds 1 to the result.
4. If the root has two children (both left and right are not null), it means the minimum depth is determined by the smaller of the two subtrees, so it recursively calls itself with both subtrees as arguments and takes the minimum of the two results, and adds 1 to it.

Suppose we have the following binary tree.

The minimum depth of this tree is 2 because the shortest path from the root to a leaf is [3,9]. To find this, the code does the following steps:

• It checks if the root (3) is null. It is not, so it proceeds to the next step.
• It checks if root (3) has no children. It does not, so it proceeds to the next step.
• It checks if root (3) has only one child. It does not, so it proceeds to the next step.
• It recursively calls itself with the left subtree (9) and the right subtree (20) as arguments, takes the minimum of the two results, and adds 1. This is the final return value.

To find the result of the left subtree (9), it repeats the same steps as above:

• It checks if the root (9) is null. It is not, so it proceeds to the next step.
• It checks if the root (9) has no children. It does, so it returns 1 as a result.

To find the result of the right subtree (20), it repeats the same steps as above:

• It checks if the root (20) is null. It is not, so it proceeds to the next step.
• It checks if the root (20) has no children. It does not, so it proceeds to the next step.
• It checks if the root (20) has only one child. It does not, so it proceeds to the next step.
• It recursively calls itself with the left subtree (15) and the right subtree (7) as arguments and takes the minimum of the two results, and adds 1 to it. This is the return value for this subtree.

To find the result of the left subtree (15), it repeats the same steps as above:

• It checks if the root (15) is null. It is not, so it proceeds to the next step.
• It checks if the root (15) has no children. It does, so it returns 1 as a result.

To find the result of the right subtree (7), it repeats the same steps as above:

• It checks if the root (7) is null. It is not, so it proceeds to the next step.
• It checks if root (7) has no children. It does, so it returns 1 as a result.

The minimum of the two results for the right subtree is 1, so adding 1 gives 2 as the return value for this subtree.

The minimum of the two results for the whole tree is 1 (from the left subtree), so adding 1 to it gives 2 as the final return value.

The time complexity of the code is O(n), where n is the number of nodes in the tree. This is because, in the worst case, we have to visit every node in the tree once, which takes O(n) time.