In-order Traversal of a Binary Search Tree

You are given a binary search tree (BST) represented in level order as a space-separated string. In this representation, the keyword null is used to denote a missing node. Your task is to perform an in-order traversal on the BST and output the node values in sorted order.

Recall that an in-order traversal of a binary search tree visits the left subtree, then the current node, and finally the right subtree. For a BST, this traversal produces a sorted sequence of numbers.

inputFormat

The input is provided on standard input (stdin) as a single line containing a space-separated sequence of tokens representing the level-order traversal of the tree. Each token is either an integer or the string null, where null indicates that a node is missing.

Examples:

• 1 represents a single-node tree.
• 2 1 represents a tree with root 2 and left child 1.
• 4 2 5 1 3 null 6 represents a tree with root 4, left subtree consisting of nodes 2, 1, 3, and right subtree with nodes 5 and 6 (with a missing left child for node 5).

outputFormat

Output the result of the in-order traversal as a space-separated sequence of integers to standard output (stdout). If the tree is empty, output nothing.

null