Solution 1 - Brute Force

Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Brute Force Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brute Force using `enumerate()`

Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...)).

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Using Enumerate """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for key1, num1 in enumerate(nums):
            for key2, num2 in enumerate(nums[key1 + 1 :], key1 + 1):
	              # enumerate(iterable, start=1) -> start value determines starting index
                # Printing value and key will output 1 i , 2 j, 3 k, 4 l 
                if num1 + num2 == target:
                    return [key1, key2]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 1 - DFS (Brute Force)

Traverse every node in the BST using depth-first search. For each node, check if its value falls within the inclusive range [low, high]. If so, add it to the running sum. This approach does not leverage the BST property to prune branches.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0938.1 - Solution 1 - DFS Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        """Range Sum BST Function"""
        if not root:
            return 0
        total = 0
        if low <= root.val <= high:
            total += root.val
        total += self.rangeSumBST(root.left, low, high)
        total += self.rangeSumBST(root.right, low, high)
        return total


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
    print(Solution().rangeSumBST(root, 7, 15))  # 32

    root2 = TreeNode(10, TreeNode(5, TreeNode(3, TreeNode(1)), TreeNode(7, TreeNode(6))), TreeNode(15, TreeNode(13), TreeNode(18)))
    print(Solution().rangeSumBST(root2, 6, 10))  # 23


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - DFS with BST Pruning (Recursive)

Leverage the BST property to skip entire subtrees. If the current node's value is less than low, all values in its left subtree are also less than low, so only recurse right. Similarly, if the current node's value is greater than high, only recurse left.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0938.2 - Solution 2 - DFS with BST Pruning """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        """Range Sum BST Function"""
        if not root:
            return 0
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
    print(Solution().rangeSumBST(root, 7, 15))  # 32

    root2 = TreeNode(10, TreeNode(5, TreeNode(3, TreeNode(1)), TreeNode(7, TreeNode(6))), TreeNode(15, TreeNode(13), TreeNode(18)))
    print(Solution().rangeSumBST(root2, 6, 10))  # 23


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Iterative BFS with Pruning

Use a queue (BFS) to traverse the tree iteratively. Apply the same BST pruning logic: only enqueue the left child if the current value is greater than low, and only enqueue the right child if the current value is less than high.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0938.3 - Solution 3 - Iterative BFS with Pruning """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        """Range Sum BST Function"""
        if not root:
            return 0
        total = 0
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if low <= node.val <= high:
                total += node.val
            if node.left and node.val > low:
                queue.append(node.left)
            if node.right and node.val < high:
                queue.append(node.right)
        return total


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
    print(Solution().rangeSumBST(root, 7, 15))  # 32

    root2 = TreeNode(10, TreeNode(5, TreeNode(3, TreeNode(1)), TreeNode(7, TreeNode(6))), TreeNode(15, TreeNode(13), TreeNode(18)))
    print(Solution().rangeSumBST(root2, 6, 10))  # 23


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0938 - Range Sum of BST

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - DFS (Brute Force)

Solution 2 - DFS with BST Pruning (Recursive)

Solution 3 - Iterative BFS with Pruning

Solution 2 - Brute Force using `enumerate()`