Binary Search Tree Operations

Problem

Implement a Binary Search Tree (BST) that supports three core operations: insert, search, and inorder traversal.

A Binary Search Tree is a rooted binary tree where, for every node:

• All values in the left subtree are strictly less than the node's value.
• All values in the right subtree are strictly greater than the node's value.
• No duplicate values are inserted.

Operations

You will be given a list of operations to perform on an initially empty BST. Each operation is one of:

• ["insert", val] — Insert val into the BST. If val already exists, do nothing.
• ["search", val] — Return true if val exists in the BST, false otherwise.
• ["inorder"] — Return the in-order traversal of the BST as a sorted list of integers.

Input / Output Format

Input: A list of operations, where each operation is a list. The first element is the operation name (string), and the second element (if present) is the integer value.

Output: A list of results for each operation:

• insert operations return null.
• search operations return true or false.
• inorder operations return a list of integers.

Examples

Example 1

Input: [["insert", 5], ["insert", 3], ["insert", 7], ["inorder"]]
Output: [null, null, null, [3, 5, 7]]

Explanation: After inserting 5, 3, and 7, the in-order traversal visits nodes in ascending order: 3 → 5 → 7.

Example 2

Input: [["insert", 10], ["search", 10], ["search", 5]]
Output: [null, true, false]

Explanation: 10 is inserted, so searching for 10 returns true. Since 5 was never inserted, searching for 5 returns false.

Example 3

Input: [["insert", 4], ["insert", 2], ["insert", 6], ["insert", 1], ["insert", 3], ["insert", 2], ["inorder"], ["search", 3]]
Output: [null, null, null, null, null, null, [1, 2, 3, 4, 6], [3, 5, 7]]
Output: [null, null, null, null, null, null, [1, 2, 3, 4, 6], true]

Explanation: Inserting duplicate 2 is ignored. In-order traversal returns sorted unique elements. Searching for 3 returns true.

Approach Hints

• Node Structure: Each node holds a val, a left child, and a right child.
• Insert: Recursively (or iteratively) traverse left if val < node.val, right if val > node.val, and place the new node when you reach null.
• Search: Similarly traverse the tree comparing values until you find a match or reach null.
• In-order Traversal: Recursively visit left subtree → current node → right subtree. This always yields a sorted sequence for a valid BST.