Maximum Depth of Binary Tree

🏠 ⬅️ ➡️

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

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

Example 2:

Input: root = [1,null,2] Output: 2

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -100 <= Node.val <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program max_depth
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none

    type, public :: node_t
        real(kind=DP) :: val
        class(node_t), pointer :: left => null()
        class(node_t), pointer :: right => null()
    end type

    interface
        function max_depth_recursive(root) result(res)
            import :: node_t
            class(node_t), intent(in) :: root
            integer :: res
        end function

        function max_depth_iterative(root) result(res)
            import :: node_t
            class(node_t), intent(in) :: root
            integer :: res
        end function
    end interface

    type(node_t), target :: root
    integer :: res

    call test_max_depth(root)

contains

    subroutine test_max_depth(root)
        type(node_t), intent(inout) :: root

        write (unit=error_unit, fmt='(A)') 'Testing recursive solution...'
        res = max_depth_recursive(root)
        if (res /= 3) then
            write (unit=error_unit, fmt='(A)') 'Recursive solution failed!'
            stop 1
        else
            write (unit=error_unit, fmt='(A)') 'Recursive solution passed.'
        end if

        write (unit=error_unit, fmt='(A)') 'Testing iterative solution...'
        res = max_depth_iterative(root)
        if (res /= 3) then
            write (unit=error_unit, fmt='(A)') 'Iterative solution failed!'
            stop 1
        else
            write (unit=error_unit, fmt='(A)') 'Iterative solution passed.'
        end if
    end subroutine

    function max_depth_recursive(root) result(res)
        class(node_t), intent(in) :: root
        integer :: res

        if (.not. associated(root)) then
            res = 0
        else
            res = 1 + max(max_depth_recursive(root%left), max_depth_recursive(root%right))
        end if
    end function

    function max_depth_iterative(root) result(res)
        class(node_t), intent(in) :: root
        integer :: res

        type(node_t), pointer :: current => root
        integer :: level, max_level

        do while (associated(current))
            level = 0
            do while (associated(current))
                level = level + 1
                current => current%left
            end do
            max_level = max(max_level, level)
            current => root
            level = 0
            do while (associated(current))
                level = level + 1
                current => current%right
            end do
            max_level = max(max_level, level)
        end do

        res = max_level
    end function
end program
❌ Compiled
❌ Executed
❌ Correct 
module BinaryTree

    implicit none

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

    interface
        function max_depth(root) result(depth)
            type(Node), pointer, intent(in) :: root
            integer :: depth
        end function max_depth
    end interface

contains

    function max_depth(root) result(depth)
        type(Node), pointer, intent(in) :: root
        integer :: depth
        if (associated(root)) then
            depth = max(max_depth(root%left), max_depth(root%right)) + 1
        else
            depth = 0
        end if
    end function max_depth

end module BinaryTree

program main
    use BinaryTree
    implicit none
    type(Node), pointer :: root
    integer :: depth

    ! Example 1
    root => Node(val=3, left=Node(val=9), right=Node(val=20, left=Node(val=15), right=Node(val=7)))
    depth = max_depth(root)
    write (*,*) "Example 1:", depth

    ! Example 2
    root => Node(val=1, left=Node(val=2))
    depth = max_depth(root)
    write (*,*) "Example 2:", depth

end program main
🌐 Data from online sources 
def maxDepth(root):
    if root is None:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

The algorithm is a simple recursive traversal of the binary tree. We start from the root, and for each node, we calculate the maximum depth of its left and right subtrees. We return the maximum of these two depths plus 1 (for the current node). If the node is null, we return a depth of 0 since this path doesn't exist. This way, we traverse all potential paths in the tree and return the longest one.

🌐 Data from online sources 
int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

The algorithm is a simple recursive traversal of the binary tree. We start from the root, and for each node, we calculate the maximum depth of its left and right subtrees. We return the maximum of these two depths plus 1 (for the current node). If the node is null, we return a depth of 0 since this path doesn't exist. This way, we traverse all potential paths in the tree and return the longest one.