Challenge: Sort with a BST

Lab Python Beginner 10 points

Insert the numbers into a binary search tree in the order given (ignore duplicates), then print an inorder traversal (values separated by spaces) and the height of the tree.

Input

One line of whole numbers.

Output

Line 1: the inorder traversal. Line 2: Height: <h>

Example

Input

50 30 70 20 40 60 80

Output

20 30 40 50 60 70 80
Height: 3

Sample input available Sample output available

Editor

Python

Hints

insert(): None means you've found the spot; otherwise go left if smaller, right if bigger.

Inorder of a BST is sorted.

Solution explanation

Inserting in sorted order (test 2) makes a tall, thin tree – that's why balance matters.

Show solution

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root


values = list(map(int, input().split()))
root = None
for v in values:
    root = insert(root, v)


def inorder(n):
    return [] if n is None else inorder(n.left) + [n.value] + inorder(n.right)


def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))


print(" ".join(map(str, inorder(root))))
print("Height:", height(root))

Output

Answer