Problem 1

[10 points] Self-balancing binary search tree

Implement a self-balancing binary search tree. You are free to select any type of tree from this list:

• AVL
• Red-Black
• AA
• Scapegoat
• Splay
• Treap

range couNT Given the root node of a binary search tree (duplicates allowed), return the number of values stored in the three that are between min_val and max_val (inclusive).

 7 / \ 3 10 / \ / \ -1 5 9 12 min_val = 2, max_val = 10  5 (values in the range: 3, 5, 7, 9, 10) min_val = 3, max_val = 8  3 (values in the range: 3, 5, 7) min_val = 10, max_val = 20  2 (values in the range: 10, 12) min_val = 20, max_val = 30  0 (no values in the range)

def range_count(root, min_val, max_val):

return 0

Invert Tree

Write a function that receives the root of a binary tree as input and inverts it. Do not create a new tree, modify the one that was passed as input. Feel free to write a helper (recursive) method.

Example 1 Tree before method call: 7 / \ 3 10 / \ / \ -1 5 9 12 Tree after method call: 7 / \ 10 3 / \ / \ 12 9 5 -1 Example 2 Tree before method call: 7 / \ 3 10 / \ 9 12 Tree after method call: 7 / \ 10 3 / \ 12 9

def invert_tree(root):

return root

# Your test cases go here