Description

Please create a binary search tree, and support insert operation. Please ignore the repeat number and print out the tree with preorder, inorder and postorder sequence. (The root node is greater than the node in the left subtree and smaller than the node in the right subtree.)

Pre-order:

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

In-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Post-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Input

The input contains mutilple lines. The first line is an non-negative integer T (T<5) that specifies the number of testcases. The first line of each testcases is an integer N (N<=8000), and the second line contains N integer V (-32767<=V<32768). (The first number in the second line is the root.)

Output

Please print out the tree with preorder, inorder and postorder. (Totally three lines.)
Each lines has a newline character '\n' in the end.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss