# binary heap (min heap)

class Bin_heap:
    def __init__(self):
        self.heap_list = [0]
        self.__current_size = 0

    def build_heap(self, xs):
        i = len(xs) // 2
        self.__current_size = len(xs)
        self.heap_list = [0] + xs[:]
        while i > 0:
            self.__pop_down(i)
            i = i - 1

    def del_min(self):
        res = self.heap_list[1]
        self.heap_list[1] = self.heap_list[self.__current_size]
        self.__current_size -= 1
        self.heap_list.pop()
        self.__pop_down(1)
        return res

    def insert(self, x):
        self.heap_list.append(x)
        self.__current_size += 1
        self.__pos_item(self.__current_size)

    def find_min(self):
        return self.heap_list[1]

    def size(self):
        return self.__current_size

    def __str__(self):
        return str(print(self.heap_list[1:]))

    # private methods

    def __pos_item(self, i):
        while i // 2 > 0:
            if self.heap_list[i] < self.heap_list[i // 2]:
                tmp = self.heap_list[i // 2]
                self.heap_list[i // 2] = self.heap_list[i]
                self.heap_list[i] = tmp
            i //= 2

    def __pop_down(self, i):
        while i * 2 <= self.__current_size:
            min_ch = self.__min_child(i)
            if self.heap_list[i] > self.heap_list[min_ch]:
                tmp = self.heap_list[i]
                self.heap_list[i] = self.heap_list[min_ch]
                self.heap_list[min_ch] = tmp
            i = min_ch

    def __min_child(self, i):
        if i * 2 + 1 > self.__current_size:
            return i * 2
        else:
            if self.heap_list[i * 2] < self.heap_list[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1

# binary tree

def preorder_traversal(tree):
    if tree:
        print(tree.getRootVal())
        preorder_traversal(tree.getLeftChild())
        preorder_traversal(tree.getRightChild())


def postorder_traversal(tree):
    if tree:
        postorder_traversal(tree.getLeftChild())
        postorder_traversal(tree.getRightChild())
        print(tree.getRootVal())


def inorder_traversal(tree):
    if tree:
        inorder_traversal(tree.getLeftChild())
        print(tree.getRootVal())
        inorder_traversal(tree.getRightChild())


class BinaryTree:

    def __init__(self, rootObj):
        self.key = rootObj
        self.parent = None 
        self.leftChild = None
        self.rightChild = None

    def insert_left(self, newNode):
        if self.leftChild == None:
            t = BinaryTree(newNode)
            self.leftChild = t
            t.parent = self
        else:
            t = BinaryTree(newNode)
            t.parent = self
            t.leftChild = self.leftChild
            self.leftChild.parent = t
            self.leftChild = t

    def insert_right(self, newNode):
        if self.rightChild == None:
            t = BinaryTree(newNode)
            self.rightChild = t
            t.parent = self
        else:
            t = BinaryTree(newNode)
            t.parent = self
            t.rightChild = self.rightChild
            self.rightChild.parent = t
            self.rightChild = t

    def get_right_child(self):
        return self.rightChild

    def get_left_child(self):
        return self.leftChild

    def get_parent(self):
        return self.parent

    def set_root_val(self, obj):
        self.key = obj

    def get_root_val(self):
        return self.key