Muchos programadores y mis lectores me han estado pidiendo que comparta algunas preguntas de entrevista de codificación binaria basada en árbol, al igual que lo he hecho para la matriz, la lista vinculada, la cadena, el diseño de software, los patrones, la tabla hash y la estructura de datos en general. Esta tarea en realidad estaba pendiente por bastante tiempo y estaba atascada para mí tratando de encontrar la solución para todas y cada una de las preguntas que pude haber recopilado. Por lo tanto, decidí publicar la lista de preguntas de entrevista de árbol binario ahora y posiblemente publicar la solución como un artículo separado más adelante. Esto es como crear una interfaz y proporcionar la implementación más tarde para que no bloquee a otras personas que dependen de su interfaz (en realidad, esta es una ventaja de usar la interfaz en Java o cualquier otro lenguaje de programación).
¿Qué es la Estructura de Datos de Árbol Binario?
De todos modos, volviendo a un árbol binario, me gustaría repetir algunos de los puntos útiles sobre la estructura de datos de árbol en general que lo ayudarán a resolver estas preguntas por su cuenta:
1) Un árbol es la estructura de datos jerárquica a diferencia de una matriz o lista vinculada que son lineales. Esto significa que puede almacenar información jerárquica utilizando una estructura de datos de árbol, como una estructura de organización,un árbol genealógico, etc.
2) Un árbol tiene nodos e hijos. El nodo superior o el primer nodo se llama raíz.
3) Si desea visualizar, la estructura de datos de árbol es como un árbol invertido en el mundo real. Quiero decir, cuando ves árboles a tu alrededor, sus raíces están en la parte inferior, pero cuando dibujas una estructura de datos de árbol en programación o informática, su raíz está en la parte superior.
4) Un árbol binario es un árbol especial, donde puede tener como máximo dos hijos. Esto significa que un nodo puede no tener hijos, uno o dos hijos. No pueden tener tres hijos o más.
5) Todos los nodos que no tienen hijos se conocen como nodo hoja.
6) El árbol de búsqueda binario es un tipo especial de árbol binario donde los valores de los subárboles izquierdos son menores o iguales a la raíz y los valores de los nodos en los subárboles derechos son mayores o iguales a la raíz. Esto proporciona una estructura de ordenación a un árbol de búsqueda binario, lo que hace que la búsqueda sea realmente rápida.
También puede consultar Estructuras de datos y Algoritmos: Inmersión profunda Usando el curso Java en Udemy para obtener más información sobre los árboles de búsqueda binarios. Es uno de los mejores cursos para actualizar sus habilidades de estructura de datos y algoritmos.
7) El árbol de búsqueda binaria está estrechamente asociado con una búsqueda binaria que funciona según el principio de reducir el tamaño de entrada a la mitad después de cada iteración. Esto hace que la búsqueda sea muy rápida y puede encontrar cualquier elemento en el árbol de búsqueda binario en tiempo O (logN), pero solo si el árbol está equilibrado.
8) Hay dos formas de recorrer una estructura de datos de árbol, primero en profundidad o primero en nivel. En profundidad: primero, baja hasta que no haya más nodos para visitar y luego vuelve a visitar nodos en el mismo nivel.
Mientras está en orden de nivel, visita todos los nodos en el mismo nivel antes de pasar al siguiente nivel. También hay recorrido por pre-orden, post-orden y en-orden para binario que se usa para atravesar nodos de un árbol binario. El recorrido por orden es especial porque visita todos los nodos en orden ordenado.
9) Un árbol binario equilibrado es como tener un número igual de nodos en cada subárbol si tiene todos los nodos en el único subárbol izquierdo o derecho, su árbol binario se volverá no equilibrado y actuará como una lista vinculada, como se muestra en el diagrama a continuación:
10) Un árbol de búsqueda binario desequilibrado o no balanceado actúa como una lista enlazada donde una búsqueda tomará tiempo O(n) en lugar de tiempo O(logN) en un árbol de búsqueda binario balanceado.
Estos son algunos de los puntos importantes que todo programador debe conocer sobre la estructura de datos de árbol binario. Le ayudará a resolver problemas de codificación basados en árboles. Si quieres aprender más sobre el árbol binario y otras estructuras de datos, te sugiero que te unas a un buen curso de estructura de datos y algoritmos como Estructuras de datos y Algoritmos: Deep Dive Usando Java en Udemy para cepillar tus fundamentos.
40+ Preguntas de entrevista de árbol Binario para Programadores Java
Sin perder más tiempo, aquí está mi lista de problemas de codificación basados en árbol binario y árbol de búsqueda binaria (BST) de entrevistas de trabajo de programación. He enlazado a la solución siempre que sea posible, pero si no hay enlace, también puede encontrar una solución simplemente haciendo una búsqueda en Google. Son preguntas muy populares y muchas personas ya las han resuelto.
Para aprovechar al máximo esta lista, intente resolver el problema antes de buscar una solución, solo entonces su mente funcionará y enfrentará desafíos y consolidará su comprensión. Si miras la solución inmediatamente, solo aprenderás el 10%, pero si lo intentas, aprenderás del 80 al 90% de los conceptos y trucos detrás de cada pregunta.
1) ¿Cómo se encuentra el ancestro común más bajo de un árbol binario en Java? (solution)
2) ¿Cómo se imprime la vista izquierda de un árbol binario en Java? (solución)
3) ¿Escribir un programa para construir un árbol a partir de un recorrido por pedidos y pedidos anticipados en Java? (solución)
4) ¿Cómo se imprimen nodos comunes en dos árboles de búsqueda binarios en Java? (solución)
5) ¿Por qué el montón binario es una mejor opción que el BST para implementar la Cola de prioridad? (respuesta)
6) ¿Cómo se comprueba si un árbol binario determinado está equilibrado o no? Escriba un método Java, que acepte un árbol binario y devuelva true si está equilibrado o false de otro modo. (solución)
7) ¿Cuáles son algunas de las ventajas de un árbol de búsqueda binario sobre una estructura de datos hashtable? (respuesta)
8) ¿Cómo se comprueba si un árbol binario dado es un subárbol de otro árbol binario? (solución)
Ha dado dos árboles binarios, y necesita devolver true si un primer árbol binario es un subárbol del segundo. Un subárbol del árbol binario BT es un árbol T que consiste en un nodo de BT y todos sus descendientes. Por ejemplo, en el siguiente caso, T1 es un subárbol del árbol binario BT
9) ¿Cómo encuentra la distancia entre dos nodos en un árbol binario? (solution)
10) ¿Cómo encontrar el ancestro común más bajo en un árbol binario en Java? (solution)
11) Escribir un programa Java para comprobar si todas las hojas de un árbol binario dado están al mismo nivel? (solution)
12) ¿Cómo se convierte un árbol binario en una lista con doble enlace en Java? (solution)
13) ¿Escribir un programa para encontrar la profundidad de un árbol binario dado en Java? (solución)
14) ¿Cuál es la diferencia entre árboles de búsqueda binarios y binarios? (respuesta)
15) ¿Qué es un árbol equilibrado? (respuesta)
16) ¿Qué es el árbol AVL? (answer)
17) ¿Escribir un programa Java para imprimir el recorrido por pedido previo de un árbol de búsqueda binario? ¿Dar una solución usando iteración y recursión? (solución)
18) Imprimir el recorrido posterior al pedido de BST? Dar algoritmo iterativo y recursivo (solución)
19) ¿Imprimir el recorrido por orden de un BST en Java? Dar algoritmos iterativos y recursivos (solución)
20) Ha dado un BST, donde se intercambian dos nodos? ¿Cómo se recupera el BST original? (solución)
21) ¿Cómo se convierte un árbol binario en un árbol de búsqueda binario en Java? (solution)
22) ¿Encuentra el subárbol BST más grande de un árbol binario dado en Java? (solución)
23) ¿Escribir un programa Java para conectar nodos al mismo nivel que un árbol binario? (solución)
24) ¿Qué es una estructura de datos Trie? (respuesta)
25) ¿Cuál es la diferencia entre el árbol binario y el Trie? (answer)
26) ¿Imprimir ancestros de un nodo dado de un árbol binario en Java? (solución)
27) ¿Escribir un programa Java para imprimir el nivel de un nodo dado en un árbol binario? (solution)
28) ¿Imprimir nodos comunes de dos BST dados en Java? (solution)
29) ¿Dar un árbol binario, imprimir toda la ruta de raíz a hoja en Java? (solution)
30) ¿Imprimir el recorrido del árbol del pedido sin recursión en Java? (solución)
31) ¿Recorrido de árbol de PreOrden de impresión sin recursión y apilado en Java? (solución)
32) Imprimir recorrido de árbol PostOrder sin recursión en Java? (solution)
33) Programa Java para comprobar si un árbol binario dado es BST o no? (solución)
34) ¿Escribir un programa Java para contar nodos hoja en un árbol binario? (solución)
35) ¿Escribir un programa Java para encontrar la altura o profundidad de un árbol binario? (solución)
36) ¿Cómo se encuentra si dos árboles binarios dados son iguales? (solution)
Escriba un método en Java, que aceptará dos árboles binarios y devolverá true si son los mismos, de lo contrario devolverá false.
37) ¿Cómo se elimina un nodo dado de un árbol de búsqueda binario en Java? (solución)
38) ¿Escribir una función Java para agregar un nodo dado en un árbol de búsqueda binario? (solution)
39) ¿Imprimir un árbol binario en orden vertical en Java? (solución)
40) ¿Qué es la estructura de datos de Árbol Rojo-Negro? (answer)
El árbol Answer – Red-Black es un Árbol de Búsqueda Binario autoequilibrado (BST) donde cada nodo tiene las siguientes propiedades
a) Cada nodo tiene un color, ya sea rojo o negro.
b) La raíz del árbol siempre es negra.
c) No hay dos nodos rojos adyacentes (Un nodo rojo no puede tener un padre rojo o un hijo rojo).
d) Cada ruta desde la raíz a un nodo NULO tiene el mismo número de nodos negros.
También puede consultar Estructuras de datos en Java: Curso de Actualización de Entrevistas sobre Educación para obtener más información sobre la estructura de datos del Árbol Rojo Negro.
Eso es todo en esta lista de los 40 árboles binarios principales y los problemas de codificación basados en árbol de búsqueda binaria de las entrevistas de programación. Aunque la solución se ofrece en lenguaje de programación Java, puede resolver estas preguntas en cualquier lenguaje de programación de su elección, como Python, C, C++, JavaScript, Ruby o incluso Swift. También puede publicar su solución en la sección de comentarios para que la comunidad pueda revisar su solución y proporcionar comentarios útiles.
Todo lo mejor para su entrevista de programación.
Aprendizaje adicional
11 Preguntas Esenciales de la Entrevista de Codificación.
Domina la Entrevista de Codificación: Estructuras de datos + Algoritmos
Grokking la Entrevista de Codificación: Patrones para Preguntas de Codificación
Otras Preguntas de Entrevista de codificación l Te puede gustar
- ¿Cómo implementar el algoritmo de ordenación por inserción en Java? (tutorial)
- ¿Cómo aplicar el algoritmo Quicksort en Java? (tutorial)
- ¿Cómo implementar el algoritmo de ordenación de burbujas en Java? (tutorial)
- ¿Diferencia entre el algoritmo de clasificación basado en Comparación y No basado en comparación? (respuesta)
- ¿Cómo aplicar la ordenación de Bucket en Java? (tutorial)
- ¿Cómo implementar el algoritmo Quicksort sin recursión? (tutorial)
- ¿Cómo realizar un algoritmo de búsqueda Binaria en Java? (tutorial)
- Cómo encontrar todos los pares en una matriz cuya suma es igual a k (solución)
- ¿Cómo eliminar duplicados de una matriz en Java? (solución)
- ¿Cómo encontrar el número más significativo y más pequeño en una matriz sin ordenar? (solución)
- ¿Cómo encontrar duplicados de una matriz sin clasificar en Java? (solución)
- ¿Cómo encontrar un número faltante en una matriz ordenada? (solución)
- ¿Cómo encontrar un valor faltante de una matriz que contenga de 1 a 100? (solución)
- Más de 50 Problemas de Estructura de datos y Algoritmos de Entrevistas (preguntas)
- Mis cursos gratuitos favoritos para aprender en profundidad la estructura de datos (FreeCodeCamp)
- ¿Cómo eliminar un elemento de una matriz en Java? (solución)
- ¿Cómo comprobar si un array contiene un valor en particular? (solución)
- 10 Cursos Gratuitos de Estructura de Datos y Algoritmos para Programadores (cursos)
- Más de 100 Problemas de Codificación de Estructura de Datos de Entrevistas (preguntas)
Gracias por leer este artículo. Si te gusta este artículo, compártelo con tus amigos y colegas. Si tiene alguna pregunta o comentario, escriba una nota.
P. S.-Si está buscando algunos cursos gratuitos de Algoritmos para mejorar su comprensión de la Estructura de Datos y los Algoritmos, también debe consultar el curso de Estructuras de Datos Fáciles de Avanzadas en Udemy. Está escrito por un Ingeniero de Software y experto en Algoritmos de Google, y es completamente gratuito.