Ալգորիթմներ և Տվյալների Կառուցվածքներ

Գտնել երկրորդ ամենափոքր արժեքը BST-ում

Տրված է դատարկ փնտրման բինար ծառ (BST), որտեղ սկզբում ոչ մի գագաթ չկա։ Պետք է մշակեք հարցումների երկու տեսակ.

  1. insert x – BST-ում ներմուծել արժեքը x

  2. smallest – տպել BST-ի երկրորդ ամենափոքր տարրը

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով q հատ հարցում, պետք է կատարի վերը նշված գործողությունները։

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ q (1 ≤ q ≤ 1000)։

Հաջորդ q տողերում գտնվում են հարցումները։ Բոլոր insert հարցումների համար x֊ի արժեքի բացարձակ մեծությունը չի գերազանցում 10^9։ Իսկ բոլոր smallest հարցումների դեպքում երաշխավորված է, որ BST-ում առնվազն 2 տարր կա։

Ելք

Յուրաքանչյուր smallest հարցման համար ծրագիրը պետք է տպի BST-ի երկրորդ ամենափոքր տարրը։

Օրինակներ

Մուտք

Ելք

7
insert 2
insert 1
smallest
insert 10
smallest
insert -1
smallest

2
2
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue