Saltar al contenido

Clave más cercana en un BST

Fácil#bst#search-path~15 min

La misión

Problema

Un árbol binario de búsqueda (BST) guarda claves enteras distintas. Dada su raíz y un objetivo que puede tener parte decimal, devuelve la clave más cercana al objetivo. Si dos claves están igual de cerca, devuelve la menor. El árbol siempre tiene al menos un nodo.

Ejemplos

Input:  tree = 8, left 3 with children 1 and 6 (6 has children 4 and 7),
        right 10 with a right child 14; target = 5
Output: 4
Por qué: 4 y 6 están a uno de distancia, y 4 es el menor
Input:  same tree; target = 12.2
Output: 14
Por qué: 14 está a 1.8 de distancia, mientras que 10 está a 2.2
Input:  tree = a single node 7; target = -100
Output: 7
Por qué: caso límite: la única clave es la más cercana

Pistas

0 / 3

Tiempo objetivo
O(h)
Espacio objetivo
O(1)

Restricciones

  • keys are distinct integers
  • the tree has at least one node
  • the target may have a fractional part

¿Lo que te frena es la idea y no el código? Inserción y búsqueda en un BST lo explica.

Python 3Ctrl+Enter ejecuta