Kth Smallest in BST

Problem statement

A sorted record index is stored as a binary search tree. A librarian requests the kth record in increasing value order without needing the complete sorted export. Your task Return the kth smallest value in the valid binary search tree, using one-based rank k. Important details The tree has distinct values and k is always a valid rank. An inorder traversal visits values in sorted order, and may stop after the requested rank. Node record indices are unrelated to rank or value. Worked example For root 5 with children 3 and 7 and k = 2, the sorted order is 3, 5, 7. The second smallest value is 5.

Input format

First line: k, followed by the tree description. The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print the kth smallest value.

Constraints

1 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children. Values are distinct and form a BST; 1 <= k <= n.

Sample input

2
3
5 1 2
3 -1 -1
7 -1 -1

Sample output

5