✅99.43%🔥Easy Solution🔥With Explanation🔥
Intuition\n#### The problem requires finding the sum of values of all nodes in a binary search tree (BST) that fall within a specified range. Since it\'s a BST,
# Intuition\n#### The problem requires finding the sum of values of all nodes in a binary search tree (BST) that fall within a specified range. Since it\'s a BST, we can take advantage of its properties to efficiently identify the nodes within the given range.\n---\n\n# Approach\n#### To solve this problem, we can perform a depth-first search (DFS) traversal of the BST. At each node, we check whether its value falls within the specified range [low, high]. If the current node\'s value is within the range, we include it in the sum. We then recursively traverse the left and right subtrees.\n\n### The algorithm follows these steps:\n\n#### 1. If the current node is null, return 0.\n#### 2. If the current node\'s value is within the range [low, high], include it in the sum; otherwise, exclude it.\n#### 3. Recursively calculate the sum for the left subtree and the sum for the right subtree.\n#### 4. Return the sum of the current node, left subtree sum, and right subtree sum.\n\n---\n# Complexity\n- ## Time complexity:\n#### $$O(n)$$, where n is the number of nodes in the tree. In the worst case, we may need to visit all nodes in the tree.\n\n- ## Space complexity:\n#### $$O(h)$$, where h is the height of the tree. This represents the maximum depth of the recursive call stack. In the worst case, for an unbalanced tree, the space complexity can be $$O(n)$$, but for a balanced tree, it is $$O(log n)$$.\n---\n# Code\n```python []\nclass Solution:\n    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n        def dfs(node):\n            if not node:\n                return 0\n            \n            current_val = 0\n            if low <= node.val <= high:\n                current_val = node.val\n            \n            left_sum = dfs(node.left)\n            right_sum = dfs(node.right)\n            \n            return current_val + left_sum + right_sum\n        \n        return dfs(root)\n```\n```java []\npublic class Solution {\n    public int rangeSumBST(TreeNode root, int low, int high) {\n        if (root == null) {\n            return 0;\n        }\n\n        int currentVal = (root.val >= low && root.val <= high) ? root.val : 0;\n\n        int leftSum = rangeSumBST(root.left, low, high);\n        int rightSum = rangeSumBST(root.right, low, high);\n\n        return currentVal + leftSum + rightSum;\n    }\n}\n```\n```javascript []\nvar rangeSumBST = function(root, low, high) {\n    if (!root) {\n        return 0;\n    }\n\n    const currentVal = (root.val >= low && root.val <= high) ? root.val : 0;\n\n    const leftSum = rangeSumBST(root.left, low, high);\n    const rightSum = rangeSumBST(root.right, low, high);\n\n    return currentVal + leftSum + rightSum;\n};\n```\n```C++ []\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int low, int high) {\n        if (!root) {\n            return 0;\n        }\n        \n        int currentVal = (root->val >= low && root->val <= high) ? root->val : 0;\n        \n        int leftSum = rangeSumBST(root->left, low, high);\n        int rightSum = rangeSumBST(root->right, low, high);\n        \n        return currentVal + leftSum + rightSum;\n    }\n};\n```\n```C# []\npublic class Solution {\n    public int RangeSumBST(TreeNode root, int low, int high) {\n        if (root == null) {\n            return 0;\n        }\n\n        int currentVal = (root.val >= low && root.val <= high) ? root.val : 0;\n\n        int leftSum = RangeSumBST(root.left, low, high);\n        int rightSum = RangeSumBST(root.right, low, high);\n\n        return currentVal + leftSum + rightSum;\n    }\n}\n```\n---\n![Screenshot 2023-08-20 065922.png](https://assets.leetcode.com/users/images/8754bf5a-b766-4e3f-82a1-84dfad880326_1704679966.471714.png)\n\n---
['Tree', 'Depth-First Search', 'Binary Search Tree', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']