Teaching Kids Programming – Algorithms to Compute the Range Sum of a Binary Search Tree


Teaching Kids Programming: Videos on Data Structures and Algorithms

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].

range-sum-of-bst Teaching Kids Programming - Algorithms to Compute the Range Sum of a Binary Search Tree algorithms DFS python teaching kids programming youtube video

Bruteforce Algorithm to Compute the Range Sum of a BST

We can bruteforce all the nodes and then add the answer only if the node falls in the range. The time complexity is O(N) as we need to visit N nodes exactly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0
        ans = 0
        if root.val >= low and root.val <= high:
            ans += root.val
        ans += self.rangeSumBST(root.left, low, high)
        ans += self.rangeSumBST(root.right, low, high)
        return ans
# 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: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0
        ans = 0
        if root.val >= low and root.val <= high:
            ans += root.val
        ans += self.rangeSumBST(root.left, low, high)
        ans += self.rangeSumBST(root.right, low, high)
        return ans

Recursive Depth First Search Algorithm to Compute the Range Sum of a BST

Based on above bruteforce algorithm, we can abandon half of the branch if the current value is outside the valid range. The time complexity is O(H) where H is the height of the BST – and H = Log(N) for a balanced binary search tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0
        ans = 0
        if root.val >= low and root.val <= high:
            ans += root.val
        if root.val > low:
            ans += self.rangeSumBST(root.left, low, high)
        if root.val < high:
            ans += self.rangeSumBST(root.right, low, high)
        return ans
# 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: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0
        ans = 0
        if root.val >= low and root.val <= high:
            ans += root.val
        if root.val > low:
            ans += self.rangeSumBST(root.left, low, high)
        if root.val < high:
            ans += self.rangeSumBST(root.right, low, high)
        return ans

Iterative Depth First Search Algorithm to Compute the Range Sum of a BST

We can also use the stack to perform the DFS in order to compute the range sum of a Binary Search Tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        ans = 0
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if L <= node.val <= R:
                    ans += node.val
                if L < node.val:
                    stack.append(node.left)
                if node.val < R:
                    stack.append(node.right)
        return ans
# 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: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        ans = 0
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if L <= node.val <= R:
                    ans += node.val
                if L < node.val:
                    stack.append(node.left)
                if node.val < R:
                    stack.append(node.right)
        return ans

See also other implementations of the Range Sum of BST in other programming languages:
Teaching Kids Programming – Algorithms to Compute the Range Sum of a Binary Search Tree
How to Sum within A Range in a Binary Search Tree?
GoLang: Algorithm to Compute the Range Sum of a Binary Search Tree

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
662 words
Last Post: Teaching Kids Programming - Remove Vowels from a String
Next Post: How to Get Number of CPU Cores using PHP Function (Platform Independent)

The Permanent URL is: Teaching Kids Programming – Algorithms to Compute the Range Sum of a Binary Search Tree

Leave a Reply