Binary Search Tree and Reconstruction

Frequency: Reported

Implement a binary search tree using object-oriented programming.

Required instance methods:

insert(val: int) -> null

Insert val. If it already exists, do nothing. The tree does not need to balance itself.

get_inorder() -> list[int]

Return the current values in sorted ascending order using left → root → right traversal.

get_preorder() -> list[int]

Return the current values using root → left → right traversal.

Follow-up

Implement a factory method that reconstructs a tree from its inorder and preorder traversals:

from_list(in_order: list[int], pre_order: list[int]) -> BST

The supplied answer names this factory build_tree instead. It is preserved exactly as reported, including the original test case and implementation issues such as the uninitialized root member.

Submitted C++ answer