<filename>Problems/Depth-First Search/easy/RangeSumBST/range_sum_of_bst.py
from typing import Optional

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

# def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
#     if not root:
#         return 0
#
#     if low <= root.val <= high:
#         return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)
#
#     return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)

# def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
#     if not root:
#         return 0
#     return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) + (root.val if low <= root.val <= high
#                                                                                      else 0)

# def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
#     if not root:
#         return 0
#
#     range_sum = 0
#     if root.val > low:
#         range_sum += rangeSumBST(root.left, low, high)
#     if root.val < high:
#         range_sum += rangeSumBST(root.right, low, high)
#     if low <= root.val <= high:
#         range_sum += root.val
#
#     return range_sum

def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
    stack, range_sum = [root], 0
    while stack:
        node = stack.pop()
        if node:
            stack.append(node.left)
            stack.append(node.right)
            if low <= node.val <= high:
                range_sum += node.val

    return range_sum
<filename>Problems/Depth-First Search/easy/RangeSumBST/range_sum_of_bst.py
from typing import Optional

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

# def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
#     if not root:
#         return 0
#
#     if low <= root.val <= high:
#         return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)
#
#     return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)

# def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
#     if not root:
#         return 0
#     return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) + (root.val if low <= root.val <= high
#                                                                                      else 0)

# def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
#     if not root:
#         return 0
#
#     range_sum = 0
#     if root.val > low:
#         range_sum += rangeSumBST(root.left, low, high)
#     if root.val < high:
#         range_sum += rangeSumBST(root.right, low, high)
#     if low <= root.val <= high:
#         range_sum += root.val
#
#     return range_sum

def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
    stack, range_sum = [root], 0
    while stack:
        node = stack.pop()
        if node:
            stack.append(node.left)
            stack.append(node.right)
            if low <= node.val <= high:
                range_sum += node.val

    return range_sum
# def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int: #     if not root: #         return 0 # #     if low <= root.val <= high: #         return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) # #     return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) # def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int: #     if not root: #         return 0 #     return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) + (root.val if low <= root.val <= high #                                                                                      else 0) # def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int: #     if not root: #         return 0 # #     range_sum = 0 #     if root.val > low: #         range_sum += rangeSumBST(root.left, low, high) #     if root.val < high: #         range_sum += rangeSumBST(root.right, low, high) #     if low <= root.val <= high: #         range_sum += root.val # #     return range_sum