LC 0938 [E] Range Sum of BST - ALawliet/algorithms GitHub Wiki

in-order or pre-order works the same

lo < x
lo <= x <= hi (this is the most important check to add to the result)
x < hi

inorder
if lo < x, you have room to go lower (left) until it no longer holds
if x < hi, you have room to go higher (right) until it no longer holds

class Solution:
    def rangeSumBST(self, root: TreeNode, lo: int, hi: int) -> int:   
        def inorder(x):
            if not x: return
            
            # if lo < x.val:
            inorder(x.left)

            if lo <= x.val <= hi:
                self.res += x.val 

            # if x.val < hi:
            inorder(x.right)  
        
        self.res = 0
        inorder(root)
        return self.res

class Solution:
    def rangeSumBST(self, root, low, high):
        def preorder(x):
            if not x: return

            if low <= x.val <= high:
                self.res += x.val

            # if x.val > low:
            preorder(x.left)

            # if x.val < high:
            preorder(x.right)
                
        self.res = 0
        preorder(root)
        return self.res

class Solution:
    def rangeSumBST(self, root: TreeNode, lo: int, hi: int) -> int:
        self.sum = 0
        
        def dfs(node):
            if not node.left and not node.right:
                if lo <= node.val <= hi:
                    self.sum += node.val
                return
            
            if node.left:
                dfs(node.left)

            if lo <= node.val <= hi:
                self.sum += node.val
                
            if node.right:
                dfs(node.right)
        
        dfs(root)
        return self.sum

class Solution:
    def rangeSumBST(self, root: TreeNode, lo: int, hi: int) -> int:
        if not root: return 0
        
        self.sum = 0

        if root.val > lo:
            self.sum += self.rangeSumBST(root.left, lo, hi)

        if lo <= root.val <= hi:
            self.sum += root.val 

        if root.val < hi:
            self.sum += self.rangeSumBST(root.right, lo, hi)    
            
        return self.sum

class Solution:
    def rangeSumBST(self, root: TreeNode, lo: int, hi: int) -> int:        
        def inorder(root):
            if not root: return 0
            
            sum = 0
            
            if root.val > lo:
                sum += inorder(root.left)

            if lo <= root.val <= hi:
                sum += root.val 

            if root.val < hi:
                sum += inorder(root.right)  

            return sum
        
        return inorder(root)