Problema 1: Diferencia Mínima Absoluta en un BST

Dado un árbol binario de búsqueda, hallar la diferencia absoluta mínima entre los valores de dos nodos. Aprovechando la propiedad de que un recorrido in-order produce los valores en orden ascendente, se puede calcular la diferencia entre nodos adyacentes.

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<treenode> stack = new Stack<>();
        TreeNode current = root;
        int minDiff = Integer.MAX_VALUE;
        Integer previous = null;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            if (previous != null) {
                minDiff = Math.min(minDiff, Math.abs(current.val - previous));
            }
            previous = current.val;
            current = current.right;
        }
        return minDiff;
    }
}</treenode>

Problema 2: Moda en un Árbol Binario de Búsqueda

Encontrar los elementos más frecuentes en un BST. Usando un recorrido in-order iterativo, se puede contar la frecuencia de cada valor con un mapa y luego determinar la moda basada en la frecuencia máxima.

class Solution {
    public int[] findMode(TreeNode root) {
        Stack<treenode> stack = new Stack<>();
        TreeNode node = root;
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        int highestFrequency = 0;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            int freq = frequencyMap.getOrDefault(node.val, 0) + 1;
            frequencyMap.put(node.val, freq);
            highestFrequency = Math.max(highestFrequency, freq);
            node = node.right;
        }
        List<Integer> modes = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() == highestFrequency) {
                modes.add(entry.getKey());
            }
        }
        return modes.stream().mapToInt(Integer::intValue).toArray();
    }
}</treenode>

Problema 3: Ancestro Común Más Bajo en un Árbol Binario

Dado un árbol binario y dos nodos, encontrar su ancestro común más bajo. Se emplea una búsqueda recursiva post-order: si un nodo es igual a uno de los nodos objetivo, se devuelve; de lo contrario, se combinan los resultados de los subárboles izquierdo y derecho.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
        TreeNode rightResult = lowestCommonAncestor(root.right, p, q);
        if (leftResult != null && rightResult != null) {
            return root;
        }
        return leftResult != null ? leftResult : rightResult;
    }
}

Problema 4: Ancestro Común Más Bajo en un BST

Similar al problema anterior, pero explotando las propiedades de un BST. Se itera hacia abajo comparando los valores de los nodos objetivo con el nodo actual: si ambos son mayores, se va a la derecha; si ambos son menores, a la izquierda; de lo contrario, el nodo actual es el ancestro común.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;
        while (current != null) {
            if (current.val > p.val && current.val > q.val) {
                current = current.left;
            } else if (current.val < p.val && current.val < q.val) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }
}

Problema 5: Inserción en un BST

Insertar un valor en un BST manteniendo sus propiedades. Se puede lograr iterativamente: se recorre el árbol hasta encontrar una posición vacía, comparando el valor a insertar con los nodos existentes.

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode parent = root;
        while (true) {
            if (val < parent.val) {
                if (parent.left == null) {
                    parent.left = new TreeNode(val);
                    break;
                }
                parent = parent.left;
            } else {
                if (parent.right == null) {
                    parent.right = new TreeNode(val);
                    break;
                }
                parent = parent.right;
            }
        }
        return root;
    }
}