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.