Cousins in Binary Tree

🏠 ⬅️ ➡️

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3 Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3 Output: false

Constraints:

  • The number of nodes in the tree is in the range [2, 100].
  • 1 <= Node.val <= 100
  • Each node has a unique value.
  • x != y
  • x and y are exist in the tree.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program cousinsInBinaryTree
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: UNIT_IN = 7, UNIT_OUT = 8

    type :: TreeNode
        real(kind=DP) :: val
        type(TreeNode), pointer :: left, right
    end type TreeNode

    interface
        function isCousin(root, x, y) result(res)
            import TreeNode
            type(TreeNode), target, intent(in) :: root
            real(kind=DP), intent(in) :: x, y
            logical :: res
        end function isCousin
    end interface

    type(TreeNode), pointer :: root
    real(kind=DP) :: x, y
    logical :: res

    call get_arguments()
    call solve()

contains

    subroutine get_arguments()
        read (UNIT=UNIT_IN, FMT='(L1)') x
        read (UNIT=UNIT_IN, FMT='(L1)') y
        allocate(root)
        call read_tree(root)
    end subroutine get_arguments

    subroutine solve()
        res = isCousin(root, x, y)
        write (UNIT=UNIT_OUT, FMT='(L1)') res
    end subroutine solve

    recursive subroutine read_tree(node)
        class(TreeNode), pointer, intent(out) :: node
        integer :: depth
        read (UNIT=UNIT_IN, FMT='(I1)') depth
        if (depth == 0) then
            nullify(node)
        else
            allocate(node)
            read (UNIT=UNIT_IN, FMT='(F10.0)') node%val
            call read_tree(node%left)
            call read_tree(node%right)
        end if
    end subroutine read_tree

    function isCousin(root, x, y) result(res)
        type(TreeNode), target, intent(in) :: root
        real(kind=DP), intent(in) :: x, y
        logical :: res
        type(TreeNode), pointer :: current
        integer :: depthX, depthY

        ! Find the depth of both nodes
        current => root
        do while (associated(current))
            if (current%val == x) exit
            current => current%left
        end do
        depthX = 0
        do while (associated(current))
            depthX = depthX + 1
            current => current%parent
        end do

        current => root
        do while (associated(current))
            if (current%val == y) exit
            current => current%left
        end do
        depthY = 0
        do while (associated(current))
            depthY = depthY + 1
            current => current%parent
        end do

        res = depthX /= depthY .and. depthX == depthY - 1
    end function isCousin

end program cousinsInBinaryTree
❌ Compiled
❌ Executed
❌ Correct 
module cousins
    implicit none

contains

    function is_cousins(root, x, y) result(is_cousin)
        type(node), pointer, intent(in) :: root
        integer, intent(in) :: x, y
        logical :: is_cousin

        integer :: depth_x, depth_y, parent_x, parent_y

        is_cousin = .false.

        if (root%val == x) then
            depth_x = 0
            parent_x = 0
        else
            depth_x = -1
            parent_x = -1
        end if

        if (root%val == y) then
            depth_y = 0
            parent_y = 0
        else
            depth_y = -1
            parent_y = -1
        end if

        call find_cousins(root, x, y, depth_x, depth_y, parent_x, parent_y, is_cousin)
    end function is_cousins

    recursive subroutine find_cousins(node, x, y, depth_x, depth_y, parent_x, parent_y, is_cousin)
        type(node), pointer, intent(in) :: node
        integer, intent(in) :: x, y
        integer, intent(inout) :: depth_x, depth_y, parent_x, parent_y
        logical, intent(inout) :: is_cousin

        if (associated(node)) then
            if (node%val == x) then
                depth_x = depth_y + 1
                parent_x = parent_y
            end if

            if (node%val == y) then
                depth_y = depth_x + 1
                parent_y = parent_x
            end if

            if (depth_x >= 0 .and. depth_y >= 0) then
                if (depth_x == depth_y .and. parent_x /= parent_y) then
                    is_cousin = .true.
                end if
            end if

            call find_cousins(node%left, x, y, depth_x, depth_y, parent_x, parent_y, is_cousin)
            call find_cousins(node%right, x, y, depth_x, depth_y, parent_x, parent_y, is_cousin)
        end if
    end subroutine find_cousins

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

program test
    use cousins
    implicit none

    type(node), pointer :: root
    integer :: x, y
    logical :: is_cousin

    ! Example 1
    root => create_node(1)
    root%left => create_node(2)
    root%right => create_node(3)
    root%left%left => create_node(4)
    x = 4
    y = 3
    is_cousin = is_cousins(root, x, y)
    if (is_cousin) then
        write (*,*) "Example 1: true"
    else
        write (*,*) "Example 1: false"
    end if

    ! Example 2
    root => create_node(1)
    root%left => create_node(2)
    root%right => create_node(3)
    root%left%left => create_node(4)
    root%left%right => create_node(5)
    x = 5
    y = 4
    is_cousin = is_cousins(root, x, y)
    if (is_cousin) then
        write (*,*) "Example 2: true"
    else
        write (*,*) "Example 2: false"
    end if

    ! Example 3
    root => create_node(1)
    root%left => create_node(2)
    root%right => create_node(3)
    root%left%left => create_node(4)
    x = 2
    y = 3
    is_cousin = is_cousins(root,
🌐 Data from online sources 
def tallestBillboard(rods):
    n = len(rods)
    totalLength = sum(rods)
    dp = [[-1] * (totalLength + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i in range(1, n + 1):
        for j in range(totalLength + 1):
            dp[i][j] = dp[i - 1][j]
            if rods[i - 1] <= j:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - rods[i - 1]] + rods[i - 1])
            if rods[i - 1] <= totalLength - j:
                dp[i][j] = max(dp[i][j], dp[i - 1][j + rods[i - 1]])

    return dp[n][0] // 2

The given problem can be solved using Dynamic Programming. We calculate the sum of all the lengths of rods available, this will help us in creating an NxM, where N is the number of rods and M is the sum of all lengths, table filled with "-1". Then we initialize the first row of this table with 0.

Now, we loop through the table and refer to the previous row while remaining within the boundaries of total sum. We make comparisons with the previous row values by checking if the current rod can be added to the current total length or not. If yes, we check for the maximum value by adding and updating the current value. This approach allows us to deduce the maximum equal length of rods that can be created.

Finally, we return the value at (n,0)th index divided by 2 as our final result. This gives us the largest possible height of the supported billboard. If it's not possible to support the billboard, the function returns 0.

🌐 Data from online sources 
int tallestBillboard(vector<int>& rods) {
    int n = rods.size();
    int totalLength = accumulate(rods.begin(), rods.end(), 0);
    vector<vector<int>> dp(n + 1, vector<int>(totalLength + 1, -1));
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= totalLength; j++) {
            dp[i][j] = dp[i - 1][j];
            if (rods[i - 1] <= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - rods[i - 1]] + rods[i - 1]);
            if (rods[i - 1] <= totalLength - j) dp[i][j] = max(dp[i][j], dp[i - 1][j + rods[i - 1]]);
        }
    }

    return dp[n][0] / 2;
}

The given problem can be solved using Dynamic Programming. We calculate the sum of all the lengths of rods available, this will help us in creating an NxM, where N is the number of rods and M is the sum of all lengths, table filled with "-1". Then we initialize the first row of this table with 0.

Now, we loop through the table and refer to the previous row while remaining within the boundaries of total sum. We make comparisons with the previous row values by checking if the current rod can be added to the current total length or not. If yes, we check for the maximum value by adding and updating the current value. This approach allows us to deduce the maximum equal length of rods that can be created.

Finally, we return the value at (n,0)th index divided by 2 as our final result. This gives us the largest possible height of the supported billboard. If it's not possible to support the billboard, the function returns 0.