_938. Range Sum of BST.md

938. Range Sum of BST

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 26, 2024

Last updated : July 26, 2024

---

Related Topics : Tree, Depth-First Search, Binary Search Tree, Binary Tree

Acceptance Rate : 87.14 %

---

Solutions

• e938.js
• e938.py

JavaScript

e938.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function(root, low, high) {
    function dfs(curr) {
        if (!curr) {
            return 0;
        }

        if (curr.val <= high && curr.val >= low) {
            return curr.val + dfs(curr.left) + dfs(curr.right);
        }

        if (curr.val < low) {
            return dfs(curr.right)
        }
        return dfs(curr.left);
    }

    return dfs(root)
};

Python

e938.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(curr: Optional[TreeNode], low: int, high: int) -> int :
            output = 0

            if not curr :
                return output

            if low <= curr.val <= high :
                output += curr.val + dfs(curr.left, low, high) + dfs(curr.right, low, high)
            elif curr.val < low : 
                output += dfs(curr.right, low, high)
            else :
                output += dfs(curr.left, low, high)
            return output
        return dfs(root, low, high)