Tree Traversal: Pre / In / Post-order

Tree Traversal: Pre / In / Post-order

Insert the integers into a BST in input order, then print all three depth-first traversals.

Complete preorder, inorder, postorder. Their skeletons are identical — the only difference is where visit(t) (i.e. printf("%d ", t->value);) goes:

• preorder: root → left → right
• inorder: left → root → right (for a BST this is always ascending)
• postorder: left → right → root

Input

• Line 1: integer n (n ≥ 1).
• Line 2: n space-separated integers, inserted in this order.

Output

• Line 1: preorder; line 2: inorder; line 3: postorder.
• Print a space after every number (a trailing space at end of line is fine).

Example: input 5 / 50 30 70 20 40

50 30 20 40 70 
20 30 40 50 70 
20 40 30 70 50