Поиск k-ого наименьшего элемента

/**
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution
{
    private static TreeNode Inorder(TreeNode node, ref int k)
    {
        if (node == null)
        {
            return null;
        }

        // идем влево
        TreeNode result = Inorder(node.left, ref k);
        if (result != null)
        {
            // если уже нашли k-ую наименьшую
            return result;
        }
        
        // проверяем k
        k -= 1;
        if (k == 0)
        {
            // нашли k-ую наименьшую
            return node;
        }

        // идем вправо
        return Inorder(node.right, ref k);
    }

    public static int SmallestBstElement(TreeNode root, int k)
    {
        TreeNode result = Inorder(root, ref k);
        return result.val;
    }
}

#include <vector>

using namespace std;

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

TreeNode* inorder(TreeNode* node, int& k) {
    if (node == nullptr) {
        return nullptr;
    }

    // идем влево
    TreeNode* result = inorder(node->left, k);
    if (result != nullptr) {
        // если уже нашли k-ую наименьшую
        return result;
    }
    
    // проверяем k
    k -= 1;
    if (k == 0) {
        // нашли k-ую наименьшую
        return node;
    }

    // идем вправо
    return inorder(node->right, k);
}

int smallestBstElement(TreeNode* root, int k) {
    TreeNode* result = inorder(root, k);
    return result->val;
}

package main

/**
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func inorder(node *TreeNode, k *int) *TreeNode {
    if node == nil {
        return nil
    }

    // идем влево
    result := inorder(node.Left, k)
    if result != nil {
        // если уже нашли k-ую наименьшую
        return result
    }
    
    // проверяем k
    *k -= 1
    if (*k == 0) {
        // нашли k-ую наименьшую
        return node
    }

    // идем вправо
    return inorder(node.Right, k)
}

func smallestBstElement(root *TreeNode , k int) int {
    result := inorder(root, &k)
    return result.Val
}

import java.util.*;

/**
 * class TreeNode {
 *     Integer val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(Integer val) { this.val = val; }
 *     TreeNode(Integer val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    private int index = 0;

    private TreeNode inorder(TreeNode node, int k) {
        if (node == null) {
            return null;
        }

        // идем влево
        TreeNode result = inorder(node.left, k);
        if (result != null) {
            // если уже нашли k-ую наименьшую
            return result;
        }
        
        // проверяем k
        index += 1;
        if (k == index) {
            // нашли k-ую наименьшую
            return node;
        }

        // идем вправо
        return inorder(node.right, k);
    }

    public int smallestBstElement(TreeNode root, int k) {
        TreeNode result = inorder(root, k);
        return result.val;
    }
}

from tree_node import TreeNode

# class TreeNode:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def smallest_bst_element(root: TreeNode, k: int) -> int:
    def inorder(node: TreeNode) -> int:
        if node is None:
            return None
        
        # идем влево
        result = inorder(node.left)
        if result is not None:
            # если уже нашли k-ую наименьшую
            return result
        
        # проверяем k
        #   nonlocal позволяет изменять переменную k, которая объявлена
        #   в функции smallest_bst_element
        nonlocal k
        k = k - 1
        if k == 0:
            # нашли k-ую наименьшую
            return node.val

        # идем вправо
        return inorder(node.right)

    return inorder(root)

import { TreeNode } from './treeNode.js';

/**
 * class TreeNode {
 *     constructor(val, left, right) {
 *         this.val = val;
 *         this.left = (left === undefined ? null : left);
 *         this.right = (right === undefined ? null : right);
 *     }
 * }
 */

export function inorder(node, kObj) {
    if (node === null) {
        return null;
    }

    // идем влево
    const leftResult = inorder(node.left, kObj);
    if (leftResult !== null) {
        // если уже нашли k-ую наименьшую
        return leftResult;
    }
    
    // проверяем k
    kObj.k -= 1;
    if (kObj.k === 0) {
        // нашли k-ую наименьшую
        return node;
    }

    // идем вправо
    return inorder(node.right, kObj);
}

/**
 * @param {TreeNode} root
 * @param {number} k
 * @returns {number}
 */
export function smallestBstElement(root, k) {
    const kObj = { k };
    const result = inorder(root, kObj);
    return result.val;
}