343. Kth Smallest in a Search Tree
The tree is a binary search tree. Print its kth smallest value, counting from
1. Print None if the tree has fewer than k nodes.
You already have this. The inorder traversal of a search tree comes out sorted,
so the kth smallest is the kth value that traversal produces.
Do not collect every value and sort. That throws away the ordering the tree
already gives you. Better still, stop as soon as the kth value is reached
rather than walking the rest.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - All values are distinct and the tree is a valid search tree.
Input
The first line contains two integers n and k.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root, and the tree is a search tree.
Output
Print the kth smallest value, or None if there are fewer than k nodes.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.