Diameter of Binary Tree

🏠 ⬅️ ➡️

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

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

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -100 <= Node.val <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, iostat_end, DP => REAL64
    implicit none
    integer, parameter :: unit_in = 10, unit_out = 20
    character(len=1024) :: line
    type :: node
        real(kind=DP), allocatable :: val(:)
        class(node), pointer :: left, right
    end type node
    type(node), pointer :: root
    integer :: n, i, j, status

    ! read input
    open(newunit=unit_in, file='input.txt', status='old', action='read', iostat=status)
    if (status /= 0) then
        write(error_unit, '(*(G0))') 'error: could not open input file'
        stop 1
    end if
    read(unit=unit_in, fmt=*, iostat=status) n
    allocate(root%val(n))
    do i = 1, n
        read(unit=unit_in, fmt=*, iostat=status) root%val(i)
        if (status /= 0) exit
    end do
    close(unit=unit_in)

    ! solve problem
    call solve(root)

    ! output solution
    open(newunit=unit_out, file='output.txt', status='replace', action='write', iostat=status)
    if (status /= 0) then
        write(error_unit, '(*(G0))') 'error: could not open output file'
        stop 1
    end if
    write(unit=unit_out, fmt='(I0)') diameter(root)
    close(unit=unit_out)

contains

    subroutine solve(root)
        class(node), intent(inout) :: root
        integer :: i

        ! TODO: solve the problem here

    end subroutine solve

    function diameter(root) result(res)
        class(node), intent(in) :: root
        integer :: res

        ! TODO: compute the diameter of the tree

    end function diameter

end program main
❌ Compiled
❌ Executed
❌ Correct 
module binary_tree_diameter

implicit none

private
public :: binary_tree_diameter

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

interface binary_tree_diameter
    module procedure :: binary_tree_diameter_recursive
end interface

contains

function binary_tree_diameter_recursive(root) result(diameter)
    type(binary_tree_node), pointer, intent(in) :: root
    integer :: diameter

    if (.not. associated(root)) then
        diameter = 0
        return
    end if

    ! Recursively compute the diameter of the left and right subtrees
    ! and store the maximum of these values
    diameter = max(binary_tree_diameter_recursive(root%left), binary_tree_diameter_recursive(root%right))

    ! Add the length of the path from the root to the leaf nodes
    ! to the maximum diameter
    diameter = max(diameter, binary_tree_depth(root) + binary_tree_depth(root%left) + binary_tree_depth(root%right))
end function binary_tree_diameter_recursive

function binary_tree_depth(root) result(depth)
    type(binary_tree_node), pointer, intent(in) :: root
    integer :: depth

    if (.not. associated(root)) then
        depth = 0
        return
    end if

    ! Recursively compute the depth of the left and right subtrees
    ! and store the maximum of these values
    depth = max(binary_tree_depth(root%left), binary_tree_depth(root%right)) + 1
end function binary_tree_depth

end module binary_tree_diameter

program main
    use binary_tree_diameter
    implicit none

    ! Create a binary tree with the given values
    type(binary_tree_node), pointer :: root
    root => binary_tree_node(1, null(), null())
    root%left => binary_tree_node(2, null(), null())
    root%right => binary_tree_node(3, null(), null())
    root%left%left => binary_tree_node(4, null(), null())
    root%left%right => binary_tree_node(5, null(), null())

    ! Print the diameter of the tree
    write (*,*) binary_tree_diameter(root)

end program main
🌐 Data from online sources 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter_of_binary_tree(root):
    def _diameter_of_binary_tree(node):
        if not node:
            return 0, 0
        left_height, left_diameter = _diameter_of_binary_tree(node.left)
        right_height, right_diameter = _diameter_of_binary_tree(node.right)
        height = 1 + max(left_height, right_height)
        diameter = max(left_height + right_height, max(left_diameter, right_diameter))
        return height, diameter

    return _diameter_of_binary_tree(root)[1]
  1. Create a helper function to return a tuple/array with two values:
  2. The height of the subtree rooted at the given node
  3. The largest diameter among the subtree's nodes
  4. If the node is null/None, return (0, 0), as the height and diameter are both 0.
  5. Recurse on the left and right children, obtaining their heights and diameters.
  6. The height at the current node is 1 + the maximum of the left and right heights.
  7. The diameter at the current node is the maximum of the following three values:
  8. The sum of the left and right heights (the path goes through the root)
  9. The left child's diameter
  10. The right child's diameter
  11. Return the diameter of the tree as the second element in the output tuple/array of the helper function called with the root node.
🌐 Data from online sources 
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

int diameterOfBinaryTree(TreeNode* root, int* height) {
    int leftHeight = 0, rightHeight = 0;
    if (root == nullptr) {
        *height = 0;
        return 0;
    }
    int leftDiameter = diameterOfBinaryTree(root->left, &leftHeight);
    int rightDiameter = diameterOfBinaryTree(root->right, &rightHeight);
    *height = std::max(leftHeight, rightHeight) + 1;
    return std::max(std::max(leftDiameter, rightDiameter), leftHeight + rightHeight);
}
  1. Create a helper function to return a tuple/array with two values:
  2. The height of the subtree rooted at the given node
  3. The largest diameter among the subtree's nodes
  4. If the node is null/None, return (0, 0), as the height and diameter are both 0.
  5. Recurse on the left and right children, obtaining their heights and diameters.
  6. The height at the current node is 1 + the maximum of the left and right heights.
  7. The diameter at the current node is the maximum of the following three values:
  8. The sum of the left and right heights (the path goes through the root)
  9. The left child's diameter
  10. The right child's diameter
  11. Return the diameter of the tree as the second element in the output tuple/array of the helper function called with the root node.