✅Beats 100% - Depth First Search - Explained with [ Video ] - C++/Java/Python/JS
\n\n# YouTube Video Explanation:\n\n **If you want a video for this question please write in the comments** \n\n https://www.youtube.com/watch?v=ujU-jeO1v-k \n\
![Screenshot 2024-01-08 070448.png](https://assets.leetcode.com/users/images/74a02a75-64eb-4b5a-a6ca-96debf27434e_1704678775.4148798.png)\n\n# YouTube Video Explanation:\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n<!-- https://www.youtube.com/watch?v=ujU-jeO1v-k -->\n\nhttps://youtu.be/FxQ9OlcXFdc\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 1400 Subscribers*\n*Current Subscribers: 1300*\n\n---\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the solution approach is to perform a depth-first traversal of the BST while leveraging the BST property to avoid unnecessary traversal. The steps of the approach are:\n\n1. If the current node is null (we\'ve reached a leaf\'s child), we can stop traversing this path.\n2. If the current node\'s value falls within `[low, high]`, we add it to the sum and continue to search both the left and right subtrees as there may be more nodes within the range.\n3. If the current node\'s value is less than `low`, we only need to traverse the right subtree because all values in the left subtree will also be less than `low`.\n4. If the current node\'s value is greater than `high`, we only need to traverse the left subtree, as all values in the right subtree will be greater than `high`.\n\nUsing these rules, the search efficiently skips parts of the tree that don\'t contribute to the range sum, which optimizes our algorithm significantly compared to a naive approach that checks every node.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe implementation of the solution involves the use of a recursive helper function called search, nested within the main function `rangeSumBST`. This is a common design pattern in recursive solutions, allowing the use of helper functions with additional parameters without changing the main function\'s signature. The algorithm uses this recursive function to perform a modified in-order traversal of the binary search tree. Here\'s a breakdown of how the algorithm works, with references to the data structures and patterns used:\n\n1. **Initialization**: A variable `self.ans` is initialized to 0. This will accumulate the sum of the node values that are within the range `[low, high]`.\n\n2. **Recursive Function (search)**: A nested function `search` is defined, which takes the current node as its parameter. The use of recursion is key here, enabling the function to traverse the tree depth-first.\n\n3. **Base Case**: At the beginning of the `search` function, there is a check to see if the current node is `None`. If it is, the function returns immediately. This check acts as the base case of the recursion, terminating the traversal at leaf nodes.\n\n4. **Range Check**:\n     - If the current node\'s value is within the range `[low, high]` (inclusive), the value is added to `self.ans`. As this node is within the range, there might be other nodes within the range both to the left and right, so the function recursively calls itself on both `node.left` and `node.right`.\n5. **BST Property Util5ization**:\n\n    - If the current node\'s value is less than `low`, the function calls itself recursively on `node.right` as all left child nodes of the current node are guaranteed to be out of the range.\n    - If the current node\'s value is greater than `high`, the function calls itself recursively on `node.left` as all right child nodes of the current node are guaranteed to be out of the range.\n\n6. **Starting the Traversal**: The recursive `search` function is first called on the root node to start the depth-first traversal.\n\n7. **Returning the Answer**: Finally, after the recursive calls have completed, `self.ans` contains the sum of the values within the range, and this value is returned by the `rangeSumBST` function.\n\n# Complexity\n- Time complexity: The time complexity of the function is `O(N)`, where N is the number of nodes in the binary search tree. This is because, in the worst-case scenario, the function may have to visit every node in the tree.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity of the recursion is `O(H)`, where H is the height of the tree. This complexity arises from the call stack that holds the recursive calls during the search process.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python []\n# Python3 Solution\nclass Solution:\n    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n        def dfs(node):\n            if not node:\n                return\n            if low <= node.val <= high:\n                self.total_sum += node.val\n                dfs(node.left)\n                dfs(node.right)\n            elif node.val < low:\n                dfs(node.right)\n            elif node.val > high:\n                dfs(node.left)\n\n        self.total_sum = 0\n        dfs(root)\n        return self.total_sum\n```\n```java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public int rangeSumBST(TreeNode root, int low, int high) {\n        if (root == null) {\n            return 0;\n        }\n      \n        if (low <= root.val && root.val <= high) {\n            return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);\n        } \n        else if (root.val < low) {\n            return rangeSumBST(root.right, low, high);\n        } \n        else {\n            return rangeSumBST(root.left, low, high);\n        }\n    }\n}\n```\n```C++ []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int low, int high) {\n        if (root == nullptr) {\n            return 0;\n        }\n\n        if (low <= root->val && root->val <= high) {\n            return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);\n        } else if (root->val < low) {\n            return rangeSumBST(root->right, low, high);\n        } else {\n            return rangeSumBST(root->left, low, high);\n        }\n    }\n};\n```\n```JavaScript []\n/**\n * Definition for a binary tree node.\n * function TreeNode(val, left, right) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.left = (left===undefined ? null : left)\n *     this.right = (right===undefined ? null : right)\n * }\n */\n/**\n * @param {TreeNode} root\n * @param {number} low\n * @param {number} high\n * @return {number}\n */\nvar rangeSumBST = function(root, low, high) {\n    if (root === null) {\n        return 0;\n    }\n\n    if (low <= root.val && root.val <= high) {\n        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);\n    } else if (root.val < low) {\n        return rangeSumBST(root.right, low, high);\n    } else {\n        return rangeSumBST(root.left, low, high);\n    }\n};\n\n```\n![upvote.png](https://assets.leetcode.com/users/images/143a871d-7b33-403c-bdfa-3ce5f0f8298f_1704678853.449102.png)\n
['Tree', 'Depth-First Search', 'Binary Search Tree', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']