Categoría: Binary Search Tree

Amazon entrevista Experiencia | Conjunto 134 (fuera del campus para SDE)

Posted on by Rudeus Greyrat

Me gustaría comenzar agradeciendo a toda la comunidad de GeeksforGeeks por ayudarme. Intento 1 1. Dado un número N, encuentre el número de combinación correcta de paréntesis posible. Input: N=2 => ()() Output: 2 [(()),()()] Input: N=3 => ()()() Output: 5 [()()(),((())),(())(),(()()),()(())] 2. Imprima todas las rutas de raíz a hoja utilizando un algoritmo iterativo … Continue reading «Amazon entrevista Experiencia | Conjunto 134 (fuera del campus para SDE)»

Encuentre el Node con valor mínimo en un árbol de búsqueda binaria usando recursividad

Posted on by Rudeus Greyrat

Dado un árbol de búsqueda binario , la tarea es encontrar el Node con el valor mínimo. Ejemplos:  Aporte:   Salida: 4    Enfoque: Simplemente atraviese el Node desde la raíz a la izquierda recursivamente hasta que la izquierda sea NULL. El Node cuya izquierda es NULL es el Node con el valor mínimo. A continuación se … Continue reading «Encuentre el Node con valor mínimo en un árbol de búsqueda binaria usando recursividad»

Número de aristas en la imagen especular del árbol binario completo

Posted on by Rudeus Greyrat

Dado un árbol binario completo de profundidad H . Si se toma la imagen especular del lado izquierdo y derecho de este árbol, entonces:   Imagen reflejada a la derecha: el Node más a la derecha de cada nivel está conectado al Node correspondiente reflejado. Imagen reflejada izquierda: el Node más a la izquierda de cada nivel … Continue reading «Número de aristas en la imagen especular del árbol binario completo»

Encuentre el diámetro mínimo BST que tenga una suma igual al objetivo K

Posted on by Rudeus Greyrat

Dado un árbol binario y un K objetivo , la tarea es encontrar el diámetro del subárbol mínimo que tiene una suma igual a K , que también es un árbol de búsqueda binaria. Devuelve -1 si no es posible. Ejemplos: Entrada: K = 38           13         … Continue reading «Encuentre el diámetro mínimo BST que tenga una suma igual al objetivo K»

Construir BST a partir de un recorrido de preorden dado | conjunto 2

Posted on by Rudeus Greyrat

Dado el recorrido en orden previo de un árbol de búsqueda binario, construya el BST. Por ejemplo, si el recorrido dado es {10, 5, 1, 7, 40, 50}, entonces la salida debe ser la raíz del siguiente árbol.   10 / \ 5 40 / \ \ 1 7 50 Hemos discutido las soluciones recursivas O(n^2) … Continue reading «Construir BST a partir de un recorrido de preorden dado | conjunto 2»

El valor mayor o igual más cercano en el lado izquierdo para cada elemento en la array

Posted on by Rudeus Greyrat

Dada una array de enteros, encuentre el más cercano (sin considerar la distancia, sino el valor) mayor o el mismo valor a la izquierda de cada elemento. Si un elemento no tiene un valor mayor o igual en el lado izquierdo, imprima -1. Ejemplos:   Entrada: arr[] = {10, 5, 11, 6, 20, 12}  Salida: -1, … Continue reading «El valor mayor o igual más cercano en el lado izquierdo para cada elemento en la array»

Combinar dos árboles de búsqueda binarios equilibrados

Posted on by Rudeus Greyrat

Se le proporcionan dos árboles de búsqueda binarios equilibrados, por ejemplo, AVL o Red-Black Tree. Escriba una función que fusione los dos BST balanceados dados en un árbol de búsqueda binario balanceado. Sean m elementos en el primer árbol y n elementos en el otro árbol. Su función de combinación debe tomar el tiempo O … Continue reading «Combinar dos árboles de búsqueda binarios equilibrados»

Convertir un BST normal a BST equilibrado

Posted on by Rudeus Greyrat

Dado un BST ( árbol de búsqueda binaria ) que puede estar desequilibrado, conviértalo en un BST equilibrado que tenga la altura mínima posible. Ejemplos:  C++ // C++ program to convert a left unbalanced BST to // a balanced BST #include <bits/stdc++.h> using namespace std;   struct Node {     int data;     Node* left,  *right; }; … Continue reading «Convertir un BST normal a BST equilibrado»

Inserción de árbol de búsqueda binaria con puntero principal

Posted on by Rudeus Greyrat

Hemos discutido el inserto BST simple . Cómo insertar en un árbol donde se debe mantener el puntero principal. Los punteros principales son útiles para encontrar rápidamente antepasados ​​de un Node, LCA de dos Nodes, sucesor de un Node, etc. En llamadas recursivas de inserción simple, devolvemos puntero de raíz de subárbol creado en un … Continue reading «Inserción de árbol de búsqueda binaria con puntero principal»

Compruebe si hay BST idénticos sin construir los árboles

Posted on by Rudeus Greyrat

Dadas dos arrays que representan una secuencia de claves. Imagine que hacemos un árbol de búsqueda binaria (BST) de cada array. Necesitamos decir si dos BST serán idénticos o no sin construir el árbol. Ejemplo: Por ejemplo, las arrays de entrada son {2, 4, 3, 1} y {2, 1, 4, 3} construirán el mismo árbol  … Continue reading «Compruebe si hay BST idénticos sin construir los árboles»