Range Sum of BST

🏠 ⬅️ ➡️

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 Output: 32 Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 Output: 23 Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

Constraints:

  • The number of nodes in the tree is in the range [1, 2 * 104].
  • 1 <= Node.val <= 105
  • 1 <= low <= high <= 105
  • All Node.val are unique.
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_write = 10
    type :: node_t
        real(kind=DP) :: val
        type(node_t), pointer :: left => null(), right => null()
    end type
    type(node_t), target :: root
    real(kind=DP) :: low, high
    integer :: status

    call get_args(root, low, high)

    if (root%left /= null()) then
        write (unit=unit_write, fmt='(A)', iomsg=status) 'Left child exists'
        stop 1
    end if
    if (root%right /= null()) then
        write (unit=unit_write, fmt='(A)', iomsg=status) 'Right child exists'
        stop 1
    end if

    if (root%val < low .or. root%val > high) then
        write (unit=unit_write, fmt='(A)', iomsg=status) 'Root value out of range'
        stop 1
    end if

    write (unit=unit_write, fmt='(F0.2)') root%val

contains

    subroutine get_args(root, low, high)
        type(node_t), intent(out) :: root
        real(kind=DP), intent(out) :: low, high
        character(len=1024) :: buffer
        integer :: iarg, arg_count

        arg_count = command_argument_count()
        if (arg_count /= 3) then
            write (unit=error_unit, fmt='(A)') 'Usage: ./a.out root low high'
            stop 1
        end if

        iarg = 1
        call get_command_argument(iarg, buffer)
        read (buffer, fmt=*, iomsg=status) root
        if (status /= 0) then
            write (unit=error_unit, fmt='(2A)') 'Error reading root: ', trim(buffer)
            stop 1
        end if

        iarg = iarg + 1
        call get_command_argument(iarg, buffer)
        read (buffer, fmt=*, iomsg=status) low
        if (status /= 0) then
            write (unit=error_unit, fmt='(2A)') 'Error reading low: ', trim(buffer)
            stop 1
        end if

        iarg = iarg + 1
        call get_command_argument(iarg, buffer)
        read (buffer, fmt=*, iomsg=status) high
        if (status /= 0) then
            write (unit=error_unit, fmt='(2A)') 'Error reading high: ', trim(buffer)
            stop 1
        end if
    end subroutine get_args

end program main
❌ Compiled
❌ Executed
❌ Correct 
program sum_range_binary_search_tree
      implicit none

      integer, parameter :: max_nodes = 2 * 104
      integer, parameter :: max_val = 105

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

      type(node), target :: root
      integer :: low, high
      integer :: i, j, sum

      ! Read the root node of the binary search tree
      read(*,*) root%val

      ! Read the low and high bounds
      read(*,*) low, high

      ! Initialize the sum to 0
      sum = 0

      ! Traverse the tree in order
      call traverse_tree(root, low, high, sum)

      ! Print the sum
      write(*,*) sum

      contains

      recursive subroutine traverse_tree(node, low, high, sum)
          type(node), intent(in) :: node
          integer, intent(in) :: low, high
          integer, intent(inout) :: sum

          ! Base case: if the node is null, return
          if (associated(node, null())) then
              return
          end if

          ! Recursive case: if the node value is in the range, add it to the sum and recurse
          if (node%val >= low .and. node%val <= high) then
              sum = sum + node%val
          end if

          ! Recurse on the left subtree
          call traverse_tree(node%left, low, high, sum)

          ! Recurse on the right subtree
          call traverse_tree(node%right, low, high, sum)
      end subroutine traverse_tree
      end program sum_range_binary_search_tree
🌐 Data from online sources 
from bisect import bisect_right

def num_digits_less_than_n(digits: List[int], n: int) -> int:
    ans = 0
    factor = 1
    n_str = str(n)
    for i in range(len(n_str) - 1, -1, -1):
        ans += bisect_right(digits, int(n_str[i])) * factor
        factor *= len(digits)
    return ans
  1. Initialize the answer as 0 and a factor as 1.
  2. Convert n into a string so that we can traverse each digit easily.
  3. Iterate over the digits of n from right to left.
  4. For each digit, find the number of digits less than or equal to the current digit of n using binary search, and add this number multiplied by the current factor to the answer.
  5. Multiply the factor by the number of given digits for every iteration to account for the combinations of smaller digits.
  6. Return the answer after all iterations.
🌐 Data from online sources 
#include <vector>
#include <string>
using namespace std;

int num_digits_less_than_n(vector<int>& digits, int n) {
    int ans = 0, factor = 1;
    string n_str = to_string(n);
    for (int i = n_str.size() - 1; i >= 0; --i) {
        ans += (upper_bound(digits.begin(), digits.end(), n_str[i] - '0') - digits.begin()) * factor;
        factor *= digits.size();
    }
    return ans;
}
  1. Initialize the answer as 0 and a factor as 1.
  2. Convert n into a string so that we can traverse each digit easily.
  3. Iterate over the digits of n from right to left.
  4. For each digit, find the number of digits less than or equal to the current digit of n using binary search, and add this number multiplied by the current factor to the answer.
  5. Multiply the factor by the number of given digits for every iteration to account for the combinations of smaller digits.
  6. Return the answer after all iterations.