You are given with an array of integers that contain numbers in random order. Write a program to find the longest possible sequence of consecutive numbers using the numbers from given array.

You need to return the output array which contains consecutive elements. Order of elements in the output is not important.

Best solution takes O(n) time.

If two sequences are of equal length then return the sequence starting with the number whose occurrence is earlier in the array.

Input Format :

Line 1 : Integer n, Size of array
Line 2 : Array elements (separated by space)

Constraints :

1 <= n <= 50000

Sample Input 1 :

13
2 12 9 16 10 5 3 20 25 11 1 8 6 

Sample Output 1 :

8 
9 
10 
11 
12

Sample Input 2 :

7
3 7 2 1 9 8 1

Sample Output 2 :

7
8
9
Explanation: Sequence should be of consecutive numbers. Here we have 2 sequences with same length i.e. [1, 2, 3] and [7, 8, 9], but output should be [7, 8, 9] because the starting point of [7, 8, 9] comes first in input array.

Sample Input 3 :

7
15 24 23 12 19 11 16

Sample Output 3 :

15 
16

Implement the BST class which includes following functions -

1. search

Given an element, find if that is present in BSt or not. Return true or false.

2. insert -

Given an element, insert that element in the BST at the correct position. Assume unique elements will be given.

3. delete -

Given an element, remove that element from the BST. If the element which is to be deleted has both children, replace that with the minimum element from right sub-tree.

4. printTree (recursive) -

Print the BST in ithe following format -

For printing a node with data N, you need to follow the exact format -

N:L:x,R:y

wherer, N is data of any node present in the binary tree. x and y are the values of left and right child of node N. Print the children only if it is not null.

There is no space in between.

You need to print all nodes in the recursive format in different lines.

Note : main function is given for your reference which we are using internally to test the class.

Given a binary tree, write code to create a separate linked list for each level. You need to return the array which contains head of each level linked list.

Sample Input :

5 6 10 2 3 -1 -1 -1 -1 -1 9 -1 -1

Sample Output :

5 
6 10 
2 3 
9

Given a Binary Search Tree and two integers k1 and k2, find and print the elements which are in range k1 and k2 (both inclusive).

Print the elements in increasing order.

Input format :

Line 1 : Elements in level order form (separated by space)
(If any node does not have left or right child, take -1 in its place)
Line 2 : Two Integers k1 and k2

Output Format :

Required elements (separated by space)

Sample Input :

8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
6 10

Sample Output :

6 7 8 10

Given a BST and an integer k. Find if the integer k is present in given BST or not. Return the node with data k if it is present, return null otherwise.

Assume that BST contains all unique elements.

Input Format :

Line 1 : Elements in level order form (separated by space)
(If any node does not have left or right child, take -1 in its place)
Line 2 : Integer k

Output Format :

Node with data k

Sample Input 1 :

8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
2

Sample Output 1 :

2

Sample Input 2 :

8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
12

Sample Output 2 :

(empty)

public class Solution {

/* Binary Tree Node class
 * 
 * class BinaryTreeNode<T> {
  T data;
  BinaryTreeNode<T> left;
  BinaryTreeNode<T> right;
  
  public BinaryTreeNode(T data) {
   this.data = data;
  }
 }
 */
//Main code

 public static BinaryTreeNode<Integer> searchInBST(BinaryTreeNode<Integer> root , int k){
  if(root==null)
  {
   return null;
  }
  
  if(root.data==k)
  {
   return root;
  }
  
  
  if(k<root.data)
  {
   return searchInBST(root.left ,k);
   
  }
  

   return searchInBST(root.right ,k);

 }
}