Pular para o conteúdo

Chave mais próxima em uma BST

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

A missão

Problema

Uma árvore binária de busca (BST) guarda chaves inteiras distintas. Dada a raiz dela e um alvo que pode ter parte fracionária, retorne a chave mais próxima do alvo. Se duas chaves estiverem igualmente próximas, retorne a menor. A árvore sempre tem pelo menos um nó.

Exemplos

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 e 6 estão ambos a uma unidade de distância, e 4 é o menor
Input:  same tree; target = 12.2
Output: 14
Por quê: 14 está a 1,8 de distância, enquanto 10 está a 2,2
Input:  tree = a single node 7; target = -100
Output: 7
Por quê: edge case: a única chave é a mais próxima

Dicas

0 / 3

Tempo-alvo
O(h)
Espaço-alvo
O(1)

Restrições

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

Travou na ideia, e não no código? Inserção e busca em BST explica isso.

Python 3Ctrl+Enter executa