Поиск K-ого в BST

В следующих задачах нужно найти k-ый наименьший и k-ый наибольший элемент в BST. Направленный спуск тут не поможет — нужен другой инструмент.

Посмотри на дерево ниже и попробуй применить такой алгоритм:

Если вершина пустая — возвращаемся к родителю
Идём в левого ребёнка
Добавляем значение текущей вершины в конец списка
Идём в правого ребёнка

Получится [1, 3, 4, 6, 7, 8, 10, 14] — отсортированный массив. Это не совпадение. Такой обход называется центрированным (inorder) и при запуске на BST мы всегда получим отсортированный порядок.

using System.Collections.Generic;

public class Solution
{
    public static void Inorder(TreeNode node, List<int> result)
    {
        if (node == null)
        {
            return;
        }

        Inorder(node.left, result);
        result.Add(node.val);
        Inorder(node.right, result);
    }
}

#include <vector>

using namespace std;

void inorder(TreeNode* node, vector<int>& result) {
    if (node == nullptr) {
        return;
    }

    inorder(node->left, result);
    result.push_back(node->val);
    inorder(node->right, result);
}

package main

func inorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }

    inorder(node.left, result)
    *result = append(*result, node.val)
    inorder(node.right, result)
}

import java.util.*;

public class Solution {

    public void inorder(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }

        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}

def inorder(node: TreeNode, result: list[int]):
    if node is None:
        return

    inorder(node.left, result)
    result.append(node.val)
    inorder(node.right, result)

/**
 * @param {TreeNode} node
 * @param {number[]} result
 */
export function inorder(node, result) {
  if (node === null) {
    return;
  }

  inorder(node.left, result);
  result.push(node.val);
  inorder(node.right, result);
}

Если вместо сбора в массив считать количество обойдённых элементов — можно найти k-ый наименьший или наибольший элемент без дополнительной памяти. При решении следующей задачи подумай, как это реализовать и что поменять в обходе для поиска k-ого наибольшего/наименьшего.