Question
The Archivist’s Sorted Record
In an ancient digital archive, records are stored inside a special hierarchical structure known as a Binary Search Tree (BST). You are given the root node of this archive as the starting point.
Each node contains a unique number, and the archive follows strict rules:
-
Every record stored in the left branch of a node has a smaller value than the node itself.
-
Every record stored in the right branch of a node has a larger value than the node itself.
An archivist is tasked with retrieving all the stored records in perfectly sorted order so they can be published in a catalog.
Your mission is to help the archivist by traversing the archive and returning all record values in ascending order.
Input
User Task
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function sorted_order(), which takes the root node as the input parameter.
Custom Input
The first line of input contains an integer, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function sorted_order(), which takes the root node as the input parameter.
Custom Input
The first line of input contains an integer, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Output
Return a list of integers representing the values of all nodes in sorted order.
Example
Input
8
50 25 87 12 37 62 90 -1 -1 -1 -1 -1 -1 -1 93
Output
12 25 37 50 62 87 90 93
Explanation
The below given image depicts the input binary tree:
8
50 25 87 12 37 62 90 -1 -1 -1 -1 -1 -1 -1 93
Output
12 25 37 50 62 87 90 93
Explanation
The below given image depicts the input binary tree: