Two Sum IV - Input is a BST

🏠 ⬅️ ➡️

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9 Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28 Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -104 <= Node.val <= 104
  • root is guaranteed to be a valid binary search tree.
  • -105 <= k <= 105
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 10
    type(DP), dimension(n) :: x, y
    logical :: res

    ! Example 1
    x = (/ 5._DP, 3._DP, 6._DP, 2._DP, 4._DP, -1._DP, 7._DP /)
    y = (/ 5._DP, 3._DP, 6._DP, 2._DP, 4._DP, -1._DP, 7._DP /)
    call solve(x, y, 9._DP, res)
    write (unit=error_unit, fmt='(L1)') res

    ! Example 2
    x = (/ 5._DP, 3._DP, 6._DP, 2._DP, 4._DP, -1._DP, 7._DP /)
    y = (/ 5._DP, 3._DP, 6._DP, 2._DP, 4._DP, -1._DP, 7._DP /)
    call solve(x, y, 28._DP, res)
    write (unit=error_unit, fmt='(L1)') res

contains

    subroutine solve(root, k, res)
        implicit none
        type(DP), dimension(:), intent(in) :: root
        real(kind=DP), intent(in) :: k
        logical, intent(out) :: res
        integer :: i, j

        res = .false.
        do i = 1, size(root)-1
            do j = i+1, size(root)
                if (root(i)+root(j) == k) then
                    res = .true.
                    exit
                end if
            end do
            if (res) exit
        end do
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module BSTSum
    implicit none
    private
    public :: main

contains

    logical function sumExists(root, k) result(exists)
        type(Node), pointer, intent(in) :: root
        integer, intent(in) :: k
        logical :: left, right

        exists = .false.

        if (root%left /= null()) then
            left = sumExists(root%left, k)
        else
            left = .false.
        end if

        if (root%right /= null()) then
            right = sumExists(root%right, k)
        else
            right = .false.
        end if

        if (left .or. right) then
            exists = .true.
        else
            if (root%val == k) then
                exists = .true.
            end if
        end if
    end function sumExists

    subroutine main
        type(Node), pointer :: root
        integer :: k
        logical :: exists

        ! Read the root node and the value k
        read *, root
        read *, k

        ! Call the sumExists function and print the result
        exists = sumExists(root, k)
        write (*, '(A)', advance='no') merge('True', 'False', exists)
    end subroutine main

    type :: Node
        integer :: val
        type(Node), pointer :: left
        type(Node), pointer :: right
    end type Node
end module BSTSum
🌐 Data from online sources 
def findTarget(root, k):
    nodes = set()
    return findNode(root, k, nodes)

def findNode(root, k, nodes):
    if not root:
        return False
    if k - root.val in nodes:
        return True
    nodes.add(root.val)
    return findNode(root.left, k, nodes) or findNode(root.right, k, nodes)

The function takes the root of a binary search tree and a target number k. The purpose is to see if there are two elements in the tree that sum up to k. We start by initializing a set called nodes to keep track of visited values. Then, we create a recursive helper function called findNode.

In the findNode function, the base case is when the current root is null, meaning we've reached the end of a branch, and we return false as no such pair of elements found yet. If k - root.val is found in our set, that means we've found a pair of elements that sum up to k, and we can return true. Otherwise, we proceed with the left and right children of the current root, passing the nodes set along to keep track of visited values. This is done using a depth-first search strategy.

The result is a boolean indicating whether or not two elements in the tree sum up to k.

🌐 Data from online sources 
bool findTarget(TreeNode* root, int k) {
    unordered_set<int> nodes;
    return findNode(root, k, nodes);
}

bool findNode(TreeNode* root, int k, unordered_set<int>& nodes) {
    if (!root) return false;
    if (nodes.count(k - root->val)) return true;
    nodes.insert(root->val);
    return findNode(root->left, k, nodes) || findNode(root->right, k, nodes);
}

The function takes the root of a binary search tree and a target number k. The purpose is to see if there are two elements in the tree that sum up to k. We start by initializing a set called nodes to keep track of visited values. Then, we create a recursive helper function called findNode.

In the findNode function, the base case is when the current root is null, meaning we've reached the end of a branch, and we return false as no such pair of elements found yet. If k - root.val is found in our set, that means we've found a pair of elements that sum up to k, and we can return true. Otherwise, we proceed with the left and right children of the current root, passing the nodes set along to keep track of visited values. This is done using a depth-first search strategy.

The result is a boolean indicating whether or not two elements in the tree sum up to k.