"""
Exercise 1: Range Sum of BST (LeetCode 938)

Return the sum of all node values in [low, high]. Use the BST property to
skip subtrees: if node.val < low, only the right subtree can contribute.
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def range_sum_bst(root, low, high):
    # TODO
    return 0


# --- self-check: do not modify below this line ---
def build(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        n = q.pop(0)
        if i < len(level) and level[i] is not None:
            n.left = TreeNode(level[i]); q.append(n.left)
        i += 1
        if i < len(level) and level[i] is not None:
            n.right = TreeNode(level[i]); q.append(n.right)
        i += 1
    return root

a = range_sum_bst(build([10, 5, 15, 3, 7, None, 18]), 7, 15)
b = range_sum_bst(build([10, 5, 15, 3, 7, 13, 18, 1, None, 6]), 6, 10)
print(a, b)
print("PASS" if a == 32 and b == 23 else "FAIL")