Insert the numbers, in the given order, into a binary search tree (smaller to the left, larger to the right). Print the in-order traversal, then the height of the tree.
What to build
A search tree built from input, then two questions about it.
Requirements
- Insert the numbers in the given order.
- Print the in-order traversal, then the height.
Input
The first line has n (1 to 200). The second line has n different whole numbers.
Output
Two lines: the values in order separated by spaces, then the height.
Constraints
n is from 1 to 200, and all the numbers are different.
Example
Input:
4
5 3 8 1
Output:
1 3 5 8
3
Why it works
An in-order visit goes left, then the node, then right, and in a search tree that means increasing order.
Examples
Example 1 · Input
4 5 3 8 1
Expected output
1 3 5 8 3
Example 2 · Input
1 9
Expected output
9 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
insert, inorder and height are each a few lines of recursion.
Hint 2
Sorted input makes a tall, thin tree.
Solution
Show one correct solution (try it yourself first)
class Tree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Tree(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def inorder(node):
return [] if node is None else inorder(node.left) + [node.value] + inorder(node.right)
def height(node):
return 0 if node is None else 1 + max(height(node.left), height(node.right))
n = int(input())
values = [int(x) for x in input().split()]
root = None
for v in values:
root = insert(root, v)
print(" ".join(str(v) for v in inorder(root)))
print(height(root))