Find a Corresponding Node of a Binary Tree in a Clone of That Tree

🏠 ⬅️ ➡️

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3 Output: 3 Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target = 7 Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4 Output: 4

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • The values of the nodes of the tree are unique.
  • target node is a node from the original tree and is not null.

Follow up: Could you solve the problem if repeated values on the tree are allowed?

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=256) :: filename
    type :: node
        real(kind=DP), pointer :: value => null()
        class(node), pointer :: left => null(), right => null()
    end type node
    type(node), pointer :: root, target
    integer :: stat

    ! read input file name from command line argument
    if (command_argument_count() /= 1) then
        write (unit=error_unit, fmt='(A)') 'error: expected one command line argument'
        stop 1
    end if
    call get_command_argument(1, filename)

    ! open files
    open (newunit=unit_in, file=filename, status='old', action='read', &
          access='stream', form='unformatted', iostat=stat)
    if (stat /= 0) then
        write (unit=error_unit, fmt='(A,I0,A)') 'error: could not open file "', stat, '" for reading'
        stop 2
    end if
    open (newunit=unit_out, file='stdout', status='replace', action='write', &
          access='stream', form='unformatted', iostat=stat)
    if (stat /= 0) then
        write (unit=error_unit, fmt='(A,I0,A)') 'error: could not open file "', stat, '" for writing'
        stop 3
    end if

    ! read root node from input file
    allocate (root)
    read (unit=unit_in, iostat=stat) root
    if (stat == iostat_end) then
        write (unit=error_unit, fmt='(A)') 'error: unexpected end of file while reading root node'
        stop 4
    else if (stat /= 0) then
        write (unit=error_unit, fmt='(A,I0,A)') 'error: could not read root node from file "', stat, '"'
        stop 5
    end if

    ! read target node from input file
    allocate (target)
    read (unit=unit_in, iostat=stat) target
    if (stat == iostat_end) then
        write (unit=error_unit, fmt='(A)') 'error: unexpected end of file while reading target node'
        stop 6
    else if (stat /= 0) then
        write (unit=error_unit, fmt='(A,I0,A)') 'error: could not read target node from file "', stat, '"'
        stop 7
    end if

    ! solve problem
    call solve(root, target)

    ! write solution to output file
    write (unit=unit_out) target

    ! close files
    close (unit=unit_in)
    close (unit=unit_out)

contains

subroutine solve(original, cloned)
    implicit none
    class(node), intent(in) :: original
    class(node), intent(inout) :: cloned
    ! local variables
    class(node), pointer :: current, next

    ! copy original tree into cloned tree
    allocate (cloned%left)
    allocate (cloned%right)
    allocate (cloned%value)
    cloned%value => original%value
    cloned%left => original%left
    cloned%right => original%right

    ! find target node in cloned tree
    current => cloned
    do while (associated(current))
        if (current%value == original%value) exit
        if (current%value < original%value) then
            current => current%right
        else
            current => current%left
        end if
    end do

    ! return reference to same node in cloned tree
    target => current
end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module cloned_tree

implicit none

contains

pure function find_cloned_node(original, cloned, target) result(cloned_node)

! This function finds the cloned node in the cloned tree that corresponds to the target node in the original tree.
! The function assumes that the cloned tree is a copy of the original tree.

type(node), pointer, intent(in) :: original
type(node), pointer, intent(in) :: cloned
type(node), pointer, intent(in) :: target
type(node), pointer :: cloned_node

! Initialize the cloned node to null
cloned_node => null()

! If the original tree is empty or the target node is null, return null
if (associated(original, null())) return
if (.not. associated(target, null())) return

! If the target node is the root of the original tree, return the root of the cloned tree
if (associated(target, original%left)) then
    cloned_node => cloned%left
else if (associated(target, original%right)) then
    cloned_node => cloned%right
end if

! If the target node is not the root of the original tree, find the cloned node recursively
if (.not. associated(cloned_node, null())) then
    cloned_node => find_cloned_node(original%left, cloned%left, target)
    if (.not. associated(cloned_node, null())) return
    cloned_node => find_cloned_node(original%right, cloned%right, target)
end if

end function find_cloned_node

end module cloned_tree

program main

use cloned_tree
implicit none

! Declare the original and cloned trees and the target node
type(node), pointer :: original, cloned, target

! Create the original tree
original => create_node(7)
call add_left_child(original, create_node(4))
call add_right_child(original, create_node(3))
call add_left_child(original%left, create_node(6))
call add_right_child(original%left, create_node(19))

! Create the cloned tree
cloned => create_node(7)
call add_left_child(cloned, create_node(4))
call add_right_child(cloned, create_node(3))
call add_left_child(cloned%left, create_node(6))
call add_right_child(cloned%left, create_node(19))

! Set the target node
target => original%left

! Find the cloned node
cloned_node => find_cloned_node(original, cloned, target)

! Print the value of the cloned node
write (*,*) cloned_node%data

end program main

module node_mod

implicit none

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

contains

pure function create_node(data) result(new_node)

type(node), pointer :: new_node
integer, intent(in) :: data

allocate(new_node)
new_node%data = data
new_node%left => null()
new_node%right => null()

end function create_node

subroutine add_left_child(parent, child)

type(node), pointer, intent(inout) :: parent
type(node), pointer, intent(in) :: child

if (.not. associated(parent, null())) then
    parent%left => child
end if

end subroutine add_left_child

subroutine add_right_child(parent, child)

type(node), pointer, intent(inout) :: parent
type(node), pointer, intent(in) :: child

if (.not. associated(parent, null())) then
    parent%right => child
end if

end subroutine add_right_child

end module node_mod
🌐 Data from online sources 
def reconstructMatrix(upper, lower, colsum):
    result = [[0] * len(colsum) for _ in range(2)]

    for i in range(len(colsum)):
        if colsum[i] == 2:
            result[0][i] = 1
            result[1][i] = 1
            upper -= 1
            lower -= 1
        elif colsum[i] == 1:
            if upper > lower:
                result[0][i] = 1
                upper -= 1
            else:
                result[1][i] = 1
                lower -= 1

        if upper < 0 or lower < 0:
            return []

    if upper > 0 or lower > 0:
        return []

    return result

First, initialize an empty 2D array with 2 rows and "n" columns, where "n" is the length of the colsum array.

Iterate through the colsum array, and for each element: 1. If the element is equal to 2, set both the upper row and lower row values to 1, and decrement both upper and lower. 2. If the element is equal to 1, check if upper is greater than lower. If so, set the value in the upper row to 1 and decrement upper, otherwise set the value in the lower row to 1 and decrement lower.

At any point, if either upper or lower becomes negative, return an empty array as there is no valid solution.

Finally, if either upper or lower is still greater than 0, return an empty array as there is no valid solution. Otherwise, return the reconstructed 2D array.

🌐 Data from online sources 
#include <vector>
using namespace std;

vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
    vector<vector<int>> result(2, vector<int>(colsum.size(), 0));

    for (int i = 0; i < colsum.size(); i++) {
        if (colsum[i] == 2) {
            result[0][i] = 1;
            result[1][i] = 1;
            upper--;
            lower--;
        } else if (colsum[i] == 1) {
            if (upper > lower) {
                result[0][i] = 1;
                upper--;
            } else {
                result[1][i] = 1;
                lower--;
            }
        }

        if (upper < 0 || lower < 0) {
            return {};
        }
    }

    if (upper > 0 || lower > 0) {
        return {};
    }

    return result;
}

First, initialize an empty 2D array with 2 rows and "n" columns, where "n" is the length of the colsum array.

Iterate through the colsum array, and for each element: 1. If the element is equal to 2, set both the upper row and lower row values to 1, and decrement both upper and lower. 2. If the element is equal to 1, check if upper is greater than lower. If so, set the value in the upper row to 1 and decrement upper, otherwise set the value in the lower row to 1 and decrement lower.

At any point, if either upper or lower becomes negative, return an empty array as there is no valid solution.

Finally, if either upper or lower is still greater than 0, return an empty array as there is no valid solution. Otherwise, return the reconstructed 2D array.