Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.org

README.org

Leetcode: Range Sum of BST


Range Sum of BST


Similar Problems:


Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

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

Example 2:

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

Note:

  1. The number of nodes in the tree is at most 10000.
  • The final answer is guaranteed to be less than 2^31.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/range-sum-of-bst
// Basic Idea:
// Complexity: Time O(n), Space O(1)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rangeSumBST(root *TreeNode, L int, R int) int {
    if root == nil { return 0 }
    res := 0
    if root.Val < L {
        res = rangeSumBST(root.Right, L, R)
    } else {
        if root.Val >= L && root.Val <= R {
            res = root.Val + rangeSumBST(root.Left, L, R) + rangeSumBST(root.Right, L, R)
        } else {
            res = rangeSumBST(root.Left, L, R)
        }
    }
    return res
}
linkedin
github
slack