Add to the balance function to reduce the height as much as possible. My current balance function does not seem to work with the test cases. Please help as I have spent days on this problem. Write your code within the X

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

##INTERLEAVE false class Node: # Node class def __init__(self, data): self.data = data self.left = None self.right = None

self.children = []

self.parent = None

class Tree: # Tree class def __init__(self): self.root = None

# If you need, use the space below to write any necessary helper functions here inside Tree class

XXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXXXX

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

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def update_height(node): node.height = 1 + max(update_height(node.left), update_height(node.right)) return node.height

def get_balance(node): if not node: return 0 return update_height(node.left) - update_height(node.right)

def rotate_right(y): x = y.left T2 = x.right x.right = y y.left = T2 update_height(y) update_height(x) return x

def rotate_left(x): y = x.right T2 = y.left y.left = x x.right = T2 update_height(x) update_height(y) return y

def balance_tree(node): if not node: return node

balance = get_balance(node) if balance > 1: if get_balance(node.left) < 0: node.left = rotate_left(node.left) return rotate_right(node) elif balance < -1: if get_balance(node.right) > 0: node.right = rotate_right(node.right) return rotate_left(node)

return node

#self.root = balance_tree(self.root)

XXXXXXXXXXXXXXXXXXXXXXXX

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())

Actual Output

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

Expected Output

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