Условие

Дано корневое дерево поиска (root) и целое число val. Необходимо найти узел в дереве поиска, значение которого равно val, и вернуть поддерево с этим узлом в качестве корня. Если такого узла не существует, вернуть null.

Примеры

Input: root = [4, 2, 7, 1, 3], val = 2 Output: [2, 1, 3]

Input: root = [4, 2, 7, 1, 3], val = 5 Output: []

Решение

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
 fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
    var current = root
    while (current != null) {
        when {
            current.`val` == `val` -> return current // Значение найдено
            current.`val` > `val` -> current = current.left // Идем влево
            else -> current = current.right // Идем вправо
        }
    }
    return null // Значение не найдено
}

Временная сложность

O(h), где h — высота дерева.

Пространственная сложность

O(1), так как используется итеративный подход.