Universidad Centroamericana “José Simeón Cañas”

Facultad de Ingeniería y Arquitectura

Departamento de Electrónica e Informática
Análisis de Algoritmos Ciclo 02/2023
Guía de Ejercicios No. 6 BSTs

Binary Search Trees

1. Given the following array:
A = [1, 4, 5, 10, 16, 17, 21]
Draw a BST for each of the following heights: 2, 3, 4, 5 and 6.

2. What is the difference between a Heap and a BST? Can a Heap be used to print its contents
in sorted order in O(n)? Explain your answer.

3. How could you perform an in-order walk for a BST without using recursion?

4. Suppose that we have numbers between 1 and 1000 in a BST and we want to search the
number 363. Which of the following sequences could not be the sequence of nodes visited?

a) 2, 252, 401, 398, 330, 344, 397, 363.

b) 924, 220, 911, 244, 898, 258, 362, 363.
c) 925, 202, 911, 240, 912, 245, 363.
d ) 2, 399, 387, 219, 266, 382, 381, 278, 363.
e) 935, 278, 347, 621, 299, 392, 358, 363.

5. If X is a leaf on a BST, and Y is its parent. Prove that Y is either:

a) The smallest value in the BST larger than X.

b) The largest valus in the BST smaller than X.

6. Suppose we insert a value V into a BST and the number of nodes visited is M. Then, we
search for V in the BST and the number of nodes visited is N. Prove that N = M + 1.

7. Is deletion for a BST commutative?

8. How can we sort using a BST? What would the best-case and wort-case be for this algorithm?

9. Supongamos que tenemos una función valor tal que dado un valor de tipo char (una letra
del alfabeto) devuelve un valor entero asociado a dicho identificador. Supongamos también
la existencia de un árbol de expresión T cuyos nodos hoja son letras del alfabeto y cuyos
nodos interiores son los caracteres *, +, -, /. Diseñar una función que tome como parámetros
un nodo y un árbol binario y devuelva el resultado entero de la evaluación de la expresión
representada.

10. El recorrido en preorden de un determinado árbol binario es: GEAIBMCLDFKJH y en inorden

IABEGLDCFMKHJ. a. Dibujar el árbol binario. b. Dar el recorrido en postorden. c. Diseñar
una función para dar el recorrido en postorden dado el recorrido en preorden e inorden y
escribir un programa para comprobar el resultado del apartado anterior.
11. Implementar una función no recursiva para recorrer un árbol binario en inorden.

12. Implementar una función no recursiva para recorrer un árbol binario en postorden.

13. Escribir una función recursiva que encuentre el número de nodos de un árbol binario.

14. Escribir una función recursiva que encuentre la altura de un árbol binario.

15. Escribir un procedimiento eficiente que dado un árbol binario de búsqueda y dos valores k1
y k2, escribe todos los nodos del árbol con valores k que cumplen k1 ≤ k ≤ k2. Calcular el
tiempo del algoritmo propuesto.

16. Escribir un programa que liste los nodos de un árbol binario por niveles, primero la raiz, luego
los del nivel 1, luego los del 2, etc. Debe funcionar en tiempo lineal.

17. Dos árboles binarios son similares si están los dos vacíos o tienen subárboles izquierdo y
derecho similares. Escribir una función que detecte si dos árboles binarios son similares.
¿Cuánto tarda?

18. Sean los árboles generales que contienen caracteres como valores de los nodos. Implementar
un procedimiento que escriba todos los caminos que van de la raiz a las hojas.

19. Se debe diseñar un algoritmo que lea una secuencia de palabras y determine el número de
veces que aparece cada una de ellas en la secuencia. Para ello, se dispondrá de un árbol AVL
inicialmente vacío. Cada palabra leída se buscará en el árbol; si se encuentra, se incrementará
su contador; si no, se insertará en el árbol como nueva palabra (con el contador inicializado a
1). Una vez leído el texto, se deberán escribir en pantalla, por orden alfabético, las palabras
leídas junto con el número de apariciones de cada una de ellas en la secuencia.

20. Escribe una función que dados dos árboles binarios A y B, determine si son idénticos o no.

21. Escribe una acción que dado un árbol binario A, obtenga una copia B del mismo.

22. Escribe una acción que visualice los nodos que están en el nivel n de un árbol binario.

23. Escribe una función que dado un árbol binario devuelva verdadero si el árbol es completo y
falso en otro caso.

24. Cada nodo de un árbol binario A almacena una letra alfabética. La concatenación de las
mismas, en cada camino que va desde la raíz a una hoja representa una palabra. Realizar una
acción que visualice todas las palabras almacenadas en un árbol binario A.

25. Escribe una función que indique si un árbol binario es un árbol de búsqueda.

Coding
1. Hacer una función en C++ que, dado un BST T y un entero N, borre todos los nodos cuyo
dato sea igual a N.

2. Hacer una función en C++ que, dado un árbol T, determine si es un BST válido.

3. Hacer una función en C++ que, dado un arreglo de enteros, los traslade a un BST.

4. Modificar el ejercicio anterior, para que el BST resultante sea lo más balanceado posible.
 5. Hacer una función en C++ que, dado un arreglo de enteros que representa la secuencia IN
ORDER de un BST, construya dicho BST.

6. Hacer una función en C++ que, dado un arreglo de enteros que representa la secuencia PRE
ORDER de un BST, construya dicho BST.

7. Hacer una función en C++ que, dado un arreglo de enteros que representa la secuencia POST
ORDER de un BST, construya dicho BST.

8. Hacer una función en C++ que, dado un BST y un dato, encuentre el sucesor IN ORDER
del nodo que contiene dicho dato.

9. Hacer una función en C++ que, dado un BST y un dato, encuentre el sucesor PRE ORDER
del nodo que contiene dicho dato.

10. Hacer una función en C++ que, dado un BST y un dato, encuentre el sucesor POST ORDER
del nodo que contiene dicho dato.

11. Hacer una función en C++ que, dado un BST y un dato, encuentre el antecesor IN ORDER
del nodo que contiene dicho dato.

12. Hacer una función en C++ que, dado un BST y un dato, encuentre el antecesor PRE ORDER
del nodo que contiene dicho dato.

13. Hacer una función en C++ que, dado un BST y un dato, encuentre el antecesor POST
ORDER del nodo que contiene dicho dato.

14. Hacer una función en C++ que, dado un BST y dos enteros A y B, borre del BST todos los
nodos que contengan datos en el rango [A, B].

15. Hacer una función en C++ que, dado un BST y un entero N, encuentre dos nodos en el BST
cuyos datos sumen N.

16. Hacer una función en C++ que, dado un BST de enteros, transforme el contenido de cada
nodo a su correspondiente Código ASCII.

17. Hacer una función en C++ que haga el proceso opuesto del ejercicio anterior.

18. Hacer una función en C++, que dada una lista enlazada y ordenada de enteros L, coloque
todos los datos en un BST.

19. Hacer una función en C++ que, dado un BST, lo transforme en un MIN-HEAP.

20. Hacer una función en C++ que haga el proceso opuesto del ejercicio anterior.

21. Hacer una función en C++ que, dado un BST, lo transforme en un MAX-HEAP.

22. Hacer una función en C++ que haga el proceso opuesto del ejercicio anterior.

23. Hacer una función en C++ que, dados dos BST, los fusione en uno solo.

24. Hacer una función en C++ que, dado un BST, verifique si todos los nodos tienen exactamente
1 hijo.

25. Hacer una función en C++ que, dados 2 BST, verifique si son iguales.
26. Hacer una función en C++ que, dado un BST y un entero N, encuentre el dato más grande
en el BST que sea menor o igual a N.

27. Hacer una función en C++ que, dado un BST y un entero N, encuentre el dato más pequeño
en el BST que sea mayor o igual a N.

28. Hacer una función en C++ que, dado un BST y dos datos, encuentre la distancia entre los
nodos que contengan los dos datos dados. (La distancia entre dos nodos es la cantidad de
nodos en el camino en el árbol desde el primero hasta el último).

29. Hacer una función en C++ que, dado un BST, borre todas las hojas.

30. Hacer una función en C++ que, dado un BST y un entero N, encuentre el nodo con el dato
más cercano a N.

31. Hacer una función en C++ que, dado un BST, verifique que esté completo. (Un árbol es
completo, si en el penúltimo nivel todos los nodos tienen 2 hijos).

32. Hacer una función en C++ que, dado un BST y un entero N, devuelva la profundidad del
nodo que contenga el dato N. (La profundidad es la distancia desde la raíz hasta el nodo).

33. Hacer una función en C++ que, dado un BST y dos enteros A y B, verifique si A es ancestro
de B en el BST.

34. Hacer una función en C++ que, dado un BST y un entero N, devuelva una lista enlazada
circular con todos los datos menores o iguales a N que estén en el BST.

35. Hacer una función en C++ que, dada una lista doblemente enlazada, cree un BST con los
datos de la lista recorriéndola de 2 en 2.