Binary Search Tree — Insert and Search

Practice this coding question on Coding Gurukul.

Problem statement

Implement a binary search tree using nodes with left and right child links. Start empty. - INSERT x: insert x. Ignore it if x is already present. - SEARCH x: print YES if x exists, otherwise NO. - INORDER: print all keys in increasing order, or EMPTY for an empty tree. Smaller keys belong in the left subtree; larger keys belong in the right subtree. INSERT produces no output. Use iterative traversal to handle skewed trees. O(n) time per command is allowed. Worked example After inserting 5, 2 and 8, SEARCH 2 prints YES and SEARCH 3 prints NO. INORDER prints 2 5 8.

Input format

First line: q. Next q lines: INSERT x, SEARCH x, or INORDER.

Output format

One line for each SEARCH or INORDER command.

Constraints

1 <= q <= 2000; -10^9 <= x <= 10^9. At least one output command.

Sample input

6
INSERT 5
INSERT 2
INSERT 8
SEARCH 2
SEARCH 3
INORDER

Sample output

YES
NO
2 5 8

Sign in to run or submit a solution in C++, Java or Python.