Katkat
Back

Return Binary Search Tree Values in Ascending Order

Moody'sSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to deserialize a level-order encoded Binary Search Tree into a tree structure and perform an in-order traversal to retrieve sorted values.

Problem Description

You are given a list of integers representing a Binary Search Tree (BST) serialized using level-order traversal (breadth-first search). In this representation, None (or null) values are used to indicate missing children. Your task is to reconstruct the tree and return a list of its values in ascending order.

Function Signature

def get_sorted_bst_values(level_order_list: list[int | None]) -> list[int]:

Constraints

  • The input list length is between 0 and 10^5.
  • The values in the tree are integers.
  • The tree may contain duplicates.

Examples

Example 1: Input: [4, 2, 6, 1, 3, 5, 7] Output: [1, 2, 3, 4, 5, 6, 7]

Example 2: Input: [1, None, 2, None, 3] Output: [1, 2, 3]

Considerations

  • A BST satisfies the property: for any node, all nodes in the left subtree have values less than or equal to the node's value, and all nodes in the right subtree have values greater than the node's value.
  • Ensure your solution handles skewed trees effectively (e.g., linked-list style structures).
  • Consider the trade-off between memory usage for the tree structure versus space required for the output array.

Hints

Hint 1

To reconstruct the tree, use a queue to keep track of parent nodes as you iterate through the list.

Hint 2

Once the tree is built, perform a standard in-order traversal (Left, Root, Right) to collect values in non-decreasing order.

Hint 3

If the tree structure is not strictly necessary for the result, think about whether the properties of the level-order array itself can be leveraged to avoid explicit pointer-based tree construction.

Follow-up questions

  • How would you modify your solution if the input tree was not a BST but a general binary tree?
  • Can you achieve the sorting without constructing the explicit tree objects, perhaps by utilizing the properties of heap-like array indices?
  • What are the space and time complexity implications if the tree is extremely deep (e.g., a path of 10,000 nodes)?