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 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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program min_depth_binary_tree
    implicit none

    type :: node
        integer :: val
        type(node), pointer :: left => null(), right => null()
    end type

    type(node), target :: root
    type(node), pointer :: current
    integer :: i, j, n

    ! Examples
    n = 1
    allocate(root%left)
    root%left%val = 3
    allocate(root%right)
    root%right%val = 9
    allocate(root%left%left)
    root%left%left%val = 20
    allocate(root%right%left)
    root%right%left%val = 15
    allocate(root%right%right)
    root%right%right%val = 7
    call print_min_depth(root)

    n = 2
    deallocate(root%left)
    deallocate(root%right)
    allocate(root%left)
    root%left%val = 2
    do i = 1, 5
        allocate(current%left)
        current%left%val = i
        if (i /= 5) then
            allocate(current%right)
            current%right%val = i + 1
        end if
        current => current%left
    end do
    call print_min_depth(root)

contains

    subroutine print_min_depth(root)
        type(node), intent(in) :: root
        integer :: min_depth

        min_depth = min_depth_recursive(root)
        write (*, '(A, I0)') 'Minimum depth of the binary tree is ', min_depth

    contains

        function min_depth_recursive(current) result(min_depth)
            type(node), intent(in), pointer :: current
            integer :: min_depth

            if (.not. associated(current)) then
                min_depth = 0
            else
                min_depth = 1 + min([min_depth_recursive(current%left), &
                                     min_depth_recursive(current%right)])
            end if
        end function

    end subroutine

end program
❌ Compiled
❌ Executed
❌ Correct 
module min_depth

contains

function min_depth_helper(root) result(min_depth)

! Declare variables
integer :: min_depth
type(node), pointer :: root

! Base case
if (root == null()) then
    min_depth = 0
    return
end if

! Recursive case
min_depth = 1 + min(min_depth_helper(root%left), min_depth_helper(root%right))

end function min_depth_helper

function min_depth(root) result(min_depth)

! Declare variables
integer :: min_depth
type(node), pointer :: root

! Call helper function
min_depth = min_depth_helper(root)

end function min_depth

end module min_depth

program main

use min_depth

implicit none

! Declare variables
type(node), pointer :: root
integer :: min_depth

! Create binary tree
root = new_node(3)
root%left = new_node(9)
root%right = new_node(20)
root%left%left = new_node(15)
root%left%right = new_node(7)

! Find minimum depth
min_depth = min_depth(root)

! Print minimum depth
write (*,*) "Minimum depth:", min_depth

! Free memory
call delete_node(root)

end program main

type node
    integer :: val
    type(node), pointer :: left
    type(node), pointer :: right
end type node

type(node), pointer :: new_node(val)

function new_node(val) result(node)

! Declare variables
type(node), pointer :: node
integer :: val

! Allocate memory
allocate(node)

! Set node value
node%val = val
node%left = null()
node%right = null()

end function new_node

subroutine delete_node(root)

! Declare variables
type(node), pointer :: root

! Free memory
deallocate(root)

end subroutine delete_node
🌐 Data from online sources 
def minDepth(root):
    if not root:
        return 0
    left = minDepth(root.left)
    right = minDepth(root.right)
    return (left == 0 or right == 0) and left + right + 1 or min(left, right) + 1

We perform a depth-first search on the tree. The base case would be an empty tree with a depth of 0.

For each non-null subtree, we recursively find the minimum depth of the left and right children. Then, we have three cases: 1. If both left and right children are null, then the current node is a leaf node, and the minimum depth is 1. 2. If either left or right child is null, we return the depth of the other child + 1. 3. If both children are non-null, we take the minimum depth of both children and add 1.

To handle all the cases in a single line, we use a ternary conditional expression in C++, Java, and JavaScript, and use the and-or short-circuit syntax in Python. We check if either left or right is 0, and in that case return left + right + 1 which handles cases 1 and 2; otherwise, we return the minimum depth of both children + 1, which handles case 3.

🌐 Data from online sources 
int minDepth(TreeNode* root) {
    if (!root) return 0;
    int left = minDepth(root->left);
    int right = minDepth(root->right);
    return (left == 0 || right == 0) ? left + right + 1 : min(left, right) + 1;
}

We perform a depth-first search on the tree. The base case would be an empty tree with a depth of 0.

For each non-null subtree, we recursively find the minimum depth of the left and right children. Then, we have three cases: 1. If both left and right children are null, then the current node is a leaf node, and the minimum depth is 1. 2. If either left or right child is null, we return the depth of the other child + 1. 3. If both children are non-null, we take the minimum depth of both children and add 1.

To handle all the cases in a single line, we use a ternary conditional expression in C++, Java, and JavaScript, and use the and-or short-circuit syntax in Python. We check if either left or right is 0, and in that case return left + right + 1 which handles cases 1 and 2; otherwise, we return the minimum depth of both children + 1, which handles case 3.