Description

There's an empty binary search tree, you have to implement two functions:
1. add_node: 

• If the tree is empty, the node will be the root node of this tree.
• Otherwise, start to compare with the root node, if the new node is smaller than it, compare with the leftchild, otherwise, compare with the rightchild, until there is no node to compare, place the new node.
• For example:
  • There is a binary search tree
  • 
  • add 7 to this tree
  • compare with the root
  • 
  • 7 >= 5, compare with the rightchild
  • 
  • 7 < 10, compare with the leftchild
  • 
  • 7 <= 8 and node 8 has no leftchild, so put 7 to the leftchild of node 8, the tree will be like:

​

2. showtree: output this tree in in-order

Input

The first line contains a integer n, means how many node to add.
The second line contains n number a₁ ~ a_n, means the value of n node.

 

testcases:
1. n <= 1000, 0 <= a_i <= 10⁹, the sequence of n numbers is increasing.
2. n <= 1000, 0 <= a_i <= 10⁹, the sequence of n number is decreasing.
3. n <= 1000, 0 <= a_i <= 10⁹.

Output

The output has only one line, contains n numbers, the in-order traversal of binary search tree.

please output a whitespace after every number.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13137.c

Partial Judge Header

13137.h

Tags

Add Tag

Discuss