938. Range Sum of BST

LeetCode 938. Range Sum of BST

Description

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range[low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23

Constraints:

• The number of nodes in the tree is in the range [1, 2 * 10^4].

• 1 <= Node.val <= 10^5

• 1 <= low <= high <= 10^5

• All Node.val are unique.

Tags

Tree, Depth-first Search, Recursion

Solution

In-order traverse and sum up all node values in the given range.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

func rangeSumBST(root *TreeNode, low int, high int) int {
	var ans int
	var stack []*TreeNode
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if root.Val > high {
			break
		} else if root.Val >= low {
			ans += root.Val
		}
		root = root.Right
	}
	return ans
}