from inspect import isclass
from heapq import heapify
from random import sample, random


def no_op(value):  # pragma: no cover
    return value


_node_init = no_op
_node_cls = None
_null = None
_left_attr = 'left'
_right_attr = 'right'
_parent_attr = 'parent'
_value_attr = 'value'
_id_attr = 'level_order_id'


class Node(object):
    """Represents a binary tree node."""

    def __init__(self, value, parent=_null):
        self.__setattr__(_value_attr, value)
        self.__setattr__(_left_attr, _null)
        self.__setattr__(_right_attr, _null)
        if parent is not _null and isinstance(parent, Node):
            self.__setattr__(_parent_attr, parent)
        else:
            self.__setattr__(_parent_attr, _null)

    def __repr__(self):
        return 'Node({})'.format(
            self.__getattribute__(_value_attr)
        )

    def __setattr__(self, name, value):
        # Magically set the parent to self when a child is created
        if (name in [_left_attr, _right_attr]
                and value is not _null
                and isinstance(value, Node)):
            value.parent = self
        object.__setattr__(self, name, value)

    def convert(self):
        return convert(self)

    def inspect(self):
        return inspect(self)

    def subtree(self, node_id):
        return subtree(self, node_id)

    def prune(self, node_id):
        return prune(self, node_id)

    def is_root(self):
        return self.parent is _null

    def is_leaf(self):
        return self.right is _null and self.left is _null

    def leafs(self, values_only=False):
        return leafs(self, values_only)

    def level(self):
        return 0 if self.parent == _null else self.parent.level() + 1

    def show(self):
        show(self)

    def show_ids(self):
        show_ids(self)

    def show_all(self):
        show_all(self)


def _create_node(value, parent=_null):
    """Create and return a new node."""
    if _node_init != no_op:
        return _node_init(value)
    return (_node_cls or Node)(value, parent=parent)


def _is_list(obj):
    """Return ``True`` if the object is a list, else ``False``."""
    return isinstance(obj, list)


def _is_node(obj):
    """Return ``True`` if the object is a node, else ``False``."""
    return isinstance(obj, _node_cls or Node)


def _id_of(node):
    """Return the level-order ID of the node."""
    return getattr(node, _id_attr)


def _value_of(node):
    """Return the value of the node."""
    return getattr(node, _value_attr)


def _parent_of(node):
    """Return the parent of the node."""
    return getattr(node, _parent_attr)


def _left_of(node):
    """Return the left child of the node."""
    return getattr(node, _left_attr)


def _right_o
f(node):
    """Return the right child of the node."""
    return getattr(node, _right_attr)


def _set_left(node, child):
    """Set the child to the left of the node."""
    setattr(node, _left_attr, child)


def _set_right(node, child):
    """Set the child to the right of the node."""
    setattr(node, _right_attr, child)


def _set_id(node, node_id):
    """Set the level-order ID of the node."""
    setattr
(node, _id_attr, node_id)


def _copy_with_id(node, node_id):
    """Return a copy of the node with the level-order ID injected."""
    node_copy = _create_node(_value_of(node), parent=_parent_of(node))
    _set_id(node_copy, node_id)
    return node_copy


def _prune_left(node):
    """Prune the left subtree of the node."""
    node.__setattr__(_left_attr, _null)


def _prune_right(node):
    """Prune the right subtree of the node."""
    node.__setattr__(_right_attr, _null)


def _is_balanced(node):
    """Return the depth if balanced else -1."""
    if node == _null:
        return 0

    left = _is_balanced(_left_of(node))
    if left < 0:
        return -1

    right = _is_balanced(_right_of(node))
    if right < 0 or abs(left - right) > 1:
        return -1

    return max(left, right) + 1


def _is_bst(node, min_val=float('-inf'), max_val=float('inf')):
    """Return True if and only if the tree is a binary search tree."""
    if node == _null:
        return True

    if (min_val != _null and _value_of(node) <= min_val):
        return False

    if (max_val != _null and _value_of(node) >= max_val):
        return False

    return _is_bst(_left_of(node), min_val, _value_of(node)) and \
           _is_bst(_right_of(node), _value_of(node), max_val)


def _build_list(root):
    """Build a list from a tree and return it."""
    result = []
    current_nodes = [root]
    level_not_empty = True

    while level_not_empty:
        level_not_empty = False
        next_nodes = []

        for node in current_nodes:
            if node == _null:
                result.append(_null)
                next_nodes.append(_null)
                next_nodes.append(_null)
            else:
                result.append(_value_of(node))

                left_child = _left_of(node)
                right_child = _right_of(node)

                if left_child != _null:
                    level_not_empty = True
                if right_child != _null:
                    level_not_empty = True

                next_nodes.append(left_child)
                next_nodes.append(right_child)

        current_nodes = next_nodes

    while result and result[-1] == _null:
        result.pop()
    return result


def _build_tree(values):
    """Build a tree from a list and return its root."""
    if not values:
        return _null

    nodes = [_null for _ in values]
    if values[0] == _null:
        raise ValueError('Node missing at index 0')

    root = _create_node(values[0], parent=_null)
    nodes[0] = root

    index = 1
    while index < len(values):
        value = values[index]
        if value != _null:
            parent_index = int((index + 1) / 2) - 1
            parent_node = nodes[parent_index]
            if parent_node == _null:
                raise ValueError(
                    'Node missing at index {}'
                    .format(parent_index)
                )
            child_node = _create_node(value, parent=parent_node)
            if index % 2:  # is odd
                _set_left(parent_node, child_node)
            else:
                _set_right(parent_node, child_node)
            nodes[index] = child_node
        index += 1

    return root


def _build_repr(node, with_ids=False, with_values=True):
    """Recursive function used for pretty-printing the binary tree.

    In each recursive call, a "box" of characters visually representing the
    current subtree is constructed line by line. Each line is padded with
    whitespaces to ensure all lines have the same length. The box, its width,
    and the start-end positions of its root (used for drawing branches) are
    sent up to the parent call, which then combines left and right sub-boxes
    to build a bigger box etc.
    """
    if node == _null:
        return [], 0, 0, 0

    if with_ids and with_values:
        node_repr = "{}:{}".format(_id_of(node), _value_of(node))
    elif with_ids and not with_values:
        node_repr = str(_id_of(node))
    elif not with_ids and with_values:
        node_repr = str(_value_of(node))
    else:  # pragma: no cover
        node_repr = "O"

    line1 = []
    line2 = []
    new_root_width = gap_size = len(node_repr)

    # Get the left and right sub-boxes, their widths and their root positions
    l_box, l_box_width, l_root_start, l_root_end = \
        _build_repr(_left_of(node), with_ids, with_values)
    r_box, r_box_width, r_root_start, r_root_end = \
        _build_repr(_right_of(node), with_ids, with_values)

    # Draw the branch connecting the new root to the left sub-box,
    # padding with whitespaces where necessary
    if l_box_width > 0:
        l_root = -int(-(l_root_start + l_root_end) / 2) + 1  # ceiling
        line1.append(' ' * (l_root + 1))
        line1.append('_' * (l_box_width - l_root))
        line2.append(' ' * l_root + '/')
        line2.append(' ' * (l_box_width - l_root))
        new_root_start = l_box_width + 1
        gap_size += 1
    else:
        new_root_start = 0

    # Draw the representation of t