rangeSumBST-func.py

import operator
from functools import partial

class Node:
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right
        
def lfilter(f, node):
    if not node:
        return node
    if not f(node.val):
        return lfilter(f, node.right)
    return Node(node.val, lfilter(f, node.left), lfilter(f, node.right))

def rfilter(f, node):
    if not node:
        return node
    if not f(node.val):
        return rfilter(f, node.left)
    return Node(node.val, rfilter(f, node.left), rfilter(f, node.right))

def reduce(f, node, acc):
    if not node:
        return acc
    return reduce(f, node.left, f(node.val, reduce(f, node.right, acc)))

def rangeSumBST(root, L, R):
    return reduce(operator.add,
                  rfilter(partial(operator.ge, R),
                          lfilter(partial(operator.le, L), root)),
                  0)