Given this implementation of a Binary Tree, write a function to balance the binary tree to reduce the height as much as possible.

Test #	Input	Output
1	tree = Tree() tree.add(Node(11)) tree.add(Node(27)) tree.add(Node(18)) tree.add(Node(17)) tree.add(Node(10)) tree.add(Node(30)) tree.add(Node(40)) tree.add(Node(50)) tree.add(Node(14)) tree.add(Node(13)) tree.add(Node(8)) tree.add(Node(9)) tree.balance() self.assertEquals(tree.height())	4
2	tree = Tree() tree.add(Node(6)) tree.add(Node(27)) tree.add(Node(15)) tree.add(Node(10)) tree.add(Node(13)) tree.add(Node(8)) tree.balance() self.assertEquals(tree.height())	3

def in_order_traversal(self): def dfs(node): if node: dfs(node.left) print(node.data) dfs(node.right)

dfs(self.root)

def level_order_traversal(self): if not self.root: return

queue = [self.root]

while len(queue) > 0: current_node = queue.pop(0) if current_node.left: queue.append(current_node.left) print(current_node.data) if current_node.right: queue.append(current_node.right)

def add(self,node): if not self.root: self.root = node return

def insert(root, node):

if root.data > node.data: if root.left is None: root.left = node else: insert(root.left, node) else:

if root.right is None: root.right = node else: insert(root.right, node) insert(self.root, node)

def height(self):

def get_height(node):

if node is None: return 0 else: left_height = get_height(node.left) right_height = get_height(node.right)

if left_height > right_height: return left_height +1 else: return right_height +1 return get_height(self.root)

def balance(self): """Balance the tree.""" # Add your code below to complete the tree class by adding the balance method

XXXXXXXXXXXXXXXXXXXXXXXXXXXXX

tree = Tree()

tree.add(Node(11)) tree.add(Node(27)) tree.add(Node(18)) tree.add(Node(17)) tree.add(Node(10)) tree.add(Node(30)) tree.add(Node(40)) tree.add(Node(50)) tree.add(Node(14)) tree.add(Node(13)) tree.add(Node(8)) tree.add(Node(9)) print("Height before balance:", tree.height()) tree.balance() print("Height after balance:", tree.height())

tree = Tree() # Creating a tree with only right branches; it is now a linked list. Try creating this tree by hand on a piece of paper. tree.add(Node(1)) tree.add(Node(3)) tree.add(Node(4)) tree.add(Node(5)) tree.add(Node(6)) tree.add(Node(7)) tree.add(Node(8)) tree.add(Node(9)) tree.add(Node(10)) tree.add(Node(11)) tree.add(Node(12)) tree.add(Node(13)) print("Height before balance:", tree.height()) tree.balance() print("Height after balance:", tree.height())

Expected Output:

Height before balance: 6 Height after balance: 4 Height before balance: 12 Height after balance: 4