# [LeetCode]#938. Range Sum of BST

Environment: Python 3.7

Key technique: treenode, .pop

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 = 15Output: 32`

Analysis:

1. Use treeNode class to create tree Node structure
2. We can find the search is 7–5–10–15.
3. L=7, R=15 and the answer is 10+7+15=32

Solution:

1. TreeNode class
`class Node:def __init__(self, val):self.left = None        self.right = None        self.val = valdef insert(self, val):if self.val:            if val < self.val:                if self.left is None:                    self.left = Node(val)                else:                    self.left.insert(val)            elif val > self.val:                if self.right is None:                    self.right = Node(val)                else:                    self.right.insert(val)        else:            self.val = valdef PrintTree(self):        if self.left:            self.left.PrintTree()        print( self.val),        if self.right:            self.right.PrintTree()`

2. How to use?

`root=Node(10)root.insert(5)root.insert(15)root.insert(3)root.insert(7)root.insert(18)root.PrintTree() #check tree`

3.Sum of BST.

`class Solution(object):    def rangeSumBST(self, root, L, R):        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`

Submissions:

Reference:

https://www.tutorialspoint.com/python_data_structure/python_binary_tree.htm

This is my first time to learn tree structure and it is very difficult to me.