Solution 1 - DFS with BST Pruning

If node.val < low, skip left subtree; if node.val > high, skip right subtree.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0938.1 - Range Sum of BST - Solution 1 - DFS with Pruning """

from typing import Optional

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:
        if not root:
            return 0
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

function rangeSumBST(root, low, high){
 if(!root) return 0;
 if(root.val<low) return rangeSumBST(root.right,low,high);
 if(root.val>high) return rangeSumBST(root.left,low,high);
 return root.val + rangeSumBST(root.left,low,high) + rangeSumBST(root.right,low,high);
}

function rangeSumBST(root:any, low:number, high:number):number{
 if(!root) return 0;
 if(root.val<low) return rangeSumBST(root.right,low,high);
 if(root.val>high) return rangeSumBST(root.left,low,high);
 return root.val + rangeSumBST(root.left,low,high) + rangeSumBST(root.right,low,high);
}

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func rangeSumBST(root *TreeNode, low int, high int) int {
	if root == nil {
		return 0
	}
	if root.Val < low {
		return rangeSumBST(root.Right, low, high)
	}
	if root.Val > high {
		return rangeSumBST(root.Left, low, high)
	}
	return root.Val + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
}

func main() {}

0938 - Range Sum of BST

Solution 1 - DFS with BST Pruning