0Pricing
Coding Interview Prep · Aula

K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado

Aproveite o percurso em ordem ordenado para encontrar o elemento k-ésimo menor em O(k) e somar valores em um intervalo em O(log n + k).

K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.

K-ésimo menor elemento em uma BST

K-ésimo menor elemento em uma BST (LeetCode #230) é um problema clássico que aproveita diretamente a travessia em ordem ordenada. Como a travessia em ordem visita os nós em ordem crescente, basta contar os nós durante a travessia e retornar o valor quando a contagem atingir k. O tempo é O(h + k), em que h é a altura (para alcançar o nó mais à esquerda) e k é a quantidade de etapas na travessia em ordem.

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

def kth_smallest(root, k):
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1))  # 1
print(kth_smallest(root, 2))  # 2

K-ésimo menor: iterativo com pilha

A versão iterativa usa o padrão de travessia em ordem com uma pilha explícita. Empilhe os nós à esquerda até chegar a nulo; depois, retire um nó da pilha e conte-o. Quando a contagem chegar a k, retorne o valor do nó atual. Isso evita o limite de recursão do Python para árvores muito profundas e também tem tempo O(h + k) e espaço O(h). Entrevistadores costumam pedir a versão iterativa depois da recursiva.

def kth_smallest_iterative(root, k):
    stack = []
    curr = root
    count = 0
    while curr or stack:
        while curr:             # go as far left as possible
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()      # process node
        count += 1
        if count == k:
            return curr.val
        curr = curr.right       # move to right subtree
    return -1  # k out of range

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3))  # 3

K-ésimo maior elemento em uma BST

K-ésimo maior usa a travessia em ordem inversa (direita → raiz → esquerda), que visita os nós em ordem decrescente. Conte k etapas e retorne o valor do nó atual. Isso é simétrico ao k-ésimo menor e tem tempo O(h + k). Como alternativa, calcule kth_smallest(root, total_count - k + 1) se souber o tamanho da árvore, mas a abordagem em ordem inversa é mais elegante.

def kth_largest(root, k):
    count = [0]
    result = [None]

    def reverse_inorder(node):
        if not node or result[0] is not None:
            return
        reverse_inorder(node.right)   # visit LARGER values first
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        reverse_inorder(node.left)

    reverse_inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1))  # 4 (largest)
print(kth_largest(root, 2))  # 3 (2nd largest)

Soma de intervalo em uma BST

Soma de intervalo em uma BST (LeetCode #938) pede a soma de todos os valores em [low, high]. Aproveite a propriedade da BST para eliminar ramos: se o valor do nó atual for menor que o limite inferior, toda a subárvore esquerda também estará abaixo do limite inferior — ignore-a. Se o valor atual for maior que o limite superior, ignore a subárvore direita. Isso elimina muitos ramos e é mais eficiente que uma varredura completa em ordem.

def range_sum_bst(root, low, high):
    if not root:
        return 0
    total = 0
    if low <= root.val <= high:
        total += root.val
    if root.val > low:    # left subtree might have values >= low
        total += range_sum_bst(root.left, low, high)
    if root.val < high:   # right subtree might have values <= high
        total += range_sum_bst(root.right, low, high)
    return total

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15))  # 7+10+15 = 32

Contar nós em um intervalo

Contar nós em um intervalo [low, high] segue a mesma lógica de eliminação de ramos. Uma alternativa usa bisect_left/bisect_right no vetor em ordem — mas a travessia direta da BST é O(log n + k), enquanto convertê-la primeiro em um vetor sempre custa O(n). Escolha a travessia direta, a menos que precise responder a muitas consultas de intervalo; nesse caso, construir uma BST aumentada com contagens de subárvores permite O(log n) por consulta.

def count_range(root, low, high):
    if not root:
        return 0
    count = 0
    if low <= root.val <= high:
        count += 1
    if root.val > low:
        count += count_range(root.left, low, high)
    if root.val < high:
        count += count_range(root.right, low, high)
    return count

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15))  # 7, 10, 15 = 3

BST para vetor ordenado (algoritmo completo)

Converter uma BST em um vetor ordenado leva O(n) de tempo e O(n) de espaço. Use a travessia em ordem e acrescente cada valor. Esse é o ponto de partida para problemas com várias etapas: «mesclar duas BSTs», «encontrar a mediana de uma BST» ou «verificar se duas BSTs têm a mesma sequência em ordem». O vetor resultante permite acesso O(1) por índice, pesquisa binária e técnicas de dois ponteiros, que a própria BST não consegue oferecer diretamente.

def bst_to_sorted(root):
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root))  # [1, 3, 4, 5, 6, 8, 9]

# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6))   # 4 (index of 6)

BST aumentado: tamanhos das subárvores

Um BST aumentado armazena informações adicionais em cada nó, como o tamanho de sua subárvore. Com os tamanhos das subárvores, encontrar o k-ésimo menor passa a ser O(log n): em cada nó, se o tamanho da subárvore esquerda for k-1, o nó atual será a resposta; se o tamanho da esquerda for >= k, prossiga recursivamente pela esquerda; caso contrário, subtraia e prossiga pela direita. Essa é a estrutura de dados por trás das árvores de estatísticas de ordem usadas em programação competitiva.

class AugNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.size = 1  # subtree size

def get_size(node):
    return node.size if node else 0

def update_size(node):
    if node:
        node.size = 1 + get_size(node.left) + get_size(node.right)

def kth_smallest_aug(root, k):
    left_size = get_size(root.left)
    if k == left_size + 1:
        return root.val      # current node is kth
    elif k <= left_size:
        return kth_smallest_aug(root.left, k)
    else:
        return kth_smallest_aug(root.right, k - left_size - 1)

print('Augmented BST: O(log n) kth smallest with subtree sizes')

Encontrar todos os valores em um BST entre dois nós

Para retornar todos os valores estritamente entre dois nós p e q (onde p.val < q.val), combine a travessia em ordem com a poda por intervalo: comece a coletar valores assim que passar de p.val e pare depois de q.val. Essa é uma generalização da soma em intervalo e fornece a sequência ordenada entre os dois valores consultados em O(h + k) time.

def values_between(root, low, high):
    result = []
    def inorder(node):
        if not node:
            return
        if node.val > low:    # might be values > low on left
            inorder(node.left)
        if low < node.val < high:  # strictly between
            result.append(node.val)
        if node.val < high:   # might be values < high on right
            inorder(node.right)
    inorder(root)
    return result

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15))  # [7, 10, 12]

Mediana de um BST

A mediana de um BST é o valor central da travessia em ordem. Para n nós, a mediana está no índice n // 2 (com indexação a partir de zero). Você pode coletar o vetor ordenado completo e acessá-lo pelo índice ou usar duas passagens: primeiro conte n nós, depois faça uma segunda travessia em ordem, parando no n // 2-ésimo nó. Como alternativa, use o k-ésimo menor com k = n // 2 + 1.

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def median_of_bst(root):
    n = count_nodes(root)
    if n == 0:
        return None
    k = n // 2 + 1  # (n+1)/2-th element for odd, n/2+1-th for even
    return kth_smallest(root, k)

def kth_smallest(root, k):
    count = [0]; result = [None]
    def inorder(node):
        if not node or result[0] is not None: return
        inorder(node.left)
        count[0] += 1
        if count[0] == k: result[0] = node.val; return
        inorder(node.right)
    inorder(root); return result[0]

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root))  # 4 (middle of [1,3,4,5,8])

Os k valores mais próximos do alvo

Encontre os k valores de um BST mais próximos de um alvo. Uma abordagem de dois ponteiros consiste em converter os valores em um vetor ordenado e usar uma janela deslizante de tamanho k. Como alternativa, use um montículo máximo de tamanho k, no qual você faz push das distâncias e faz pop quando o tamanho excede k. A abordagem do vetor ordenado tem complexidade O(n) time e é simples; a abordagem com montículo tem complexidade O(n log k), mas funciona em um contexto de fluxo contínuo.

import heapq

def closest_k_values(root, target, k):
    # Collect sorted values
    arr = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        arr.append(node.val)
        inorder(node.right)
    inorder(root)

    # Two-pointer sliding window of size k
    left, right = 0, k - 1
    while right < len(arr) - 1:
        if abs(arr[left] - target) <= abs(arr[right + 1] - target):
            break  # left is closer, don't advance
        left += 1
        right += 1
    return arr[left:right + 1]

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2))  # [3, 4]

Explorando a propriedade da ordem dos sucessores

Muitos problemas de BST se reduzem a encontrar o próximo ou o elemento anterior na ordem crescente — operações que levam O(log n) usando a navegação no BST. O iterador que construímos anteriormente fornece o próximo elemento em O(1) amortizado. Combinando o conhecimento sobre o k-ésimo menor, a soma em intervalo e o valor mais próximo, você pode resolver a maioria dos problemas de BST em entrevistas perguntando: "Como a ordenação da travessia em ordem simplifica este problema?" Esse padrão geral é a sua bússola para resolver problemas de BST.

# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?

# Quick reference:
# kth smallest  -> in-order, stop at kth node
# kth largest   -> reverse in-order, stop at kth node
# range sum     -> in-order + BST pruning
# closest value -> walk toward target, track best
# median        -> kth with k = n//2+1
# sorted array  -> full in-order
# validate      -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')

Verificação rápida

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.

Recapitulação da lição

Nesta lição, você aprendeu: o k-ésimo menor e o k-ésimo maior usando travessia em ordem e em ordem reversa em O(h+k), soma em intervalo com poda de BST para consultas de intervalo eficientes e conversão de um BST em um vetor ordenado como base para algoritmos baseados em vetores. Em seguida, exploraremos montículos e filas de prioridade.

Perguntas Frequentes

A aula “K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado” é grátis?

Sim — o texto completo de “K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.

O que vou aprender em “K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado”?

Aproveite o percurso em ordem ordenado para encontrar o elemento k-ésimo menor em O(k) e somar valores em um intervalo em O(log n + k). Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Coding Interview Prep?

Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.

Quanto tempo leva a aula “K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Coding Interview Prep?

Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Inserção e Busca em BST
  2. Exclusão em BST: Três Casos
  3. Validando BST e Propriedades da Ordem
  4. K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado
← Voltar para Coding Interview Prep