algorithm - Segundo máximo en BST

data-structures language-agnostic

Question

Esta es una pregunta de entrevista. Encuentra el segundo máximo en BST.

El elemento max es la hoja más a la derecha en el BST. El segundo máximo es su padre o su hijo izquierdo. Así que la solución es atravesar el BST para encontrar la hoja más a la derecha y verificar su padre e hijo izquierdo.

¿Tiene sentido?

Answer 1

El algo puede ser como sigue

1. find the largest number in the tree. 

  private static int findLargestValueInTree(Node root) {
    while (root.right != null) {
     root = root.right;
    }
    return root.data;
  }

2. Find the largest number in the tree that is smaller than the number we found in step 1

 public static int findSecondLargest(Node root, int largest, int current) {
   while (root != null) {
    if (root.data < largest) {
      current = root.data;
      root = root.right;
    } else {
      root = root.left;
   }
   }
  return current;
 }

''actual'' hace un seguimiento del número más grande actual que es más pequeño que el número encontrado en el paso 1

Answer 2

Estás cerca de la respuesta correcta.

Aquí está mi intento de una respuesta intuitiva.

El nodo más grande es el nodo más a la derecha.

Lo que esté debajo del subárbol izquierdo del nodo más a la derecha es mayor que todos los elementos excepto el nodo más a la derecha. Por lo tanto, el nodo más grande en este subárbol es la respuesta.

Si no hay un subárbol izquierdo, el padre del nodo más a la derecha es el que es mayor que todos los demás nodos, excepto el nodo más a la derecha.

Answer 3

Este algoritmo realiza una ejecución en el árbol y devuelve el elemento más grande en Item2 y el segundo más grande en Item2 . Las llamadas de ordenación son O (1) porque son independientes del tamaño del árbol. Por lo tanto, la complejidad de tiempo total es O (N) y la complejidad de espacio es O (log (N)) cuando el árbol está equilibrado.

public static Tuple<int, int> SecondLargest(TreeNode<int> node)
{
    int thisValue = node.Value;
    if ((node.Left == null || node.Left.Right == null) && node.Right == null)
    {
        return new Tuple<int, int>(thisValue, -int.MaxValue);
    }
    else if (node.Left == null || node.Left.Right == null)
    {
        Tuple<int, int> right = SecondLargest(node.Right);
        List<int> sortLargest = new List<int>(new int[] { right.Item1, right.Item2, thisValue });
        sortLargest.Sort();
        return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
    }
    else if (node.Right == null)
    {
        Tuple<int, int> left = SecondLargest(node.Left.Right);
        List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, thisValue });
        sortLargest.Sort();
        return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
    }
    else
    {
        Tuple<int, int> left = SecondLargest(node.Left.Right);
        Tuple<int, int> right = SecondLargest(node.Right);
        List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, right.Item1, right.Item2, thisValue });
        sortLargest.Sort();
        return new Tuple<int, int>(sortLargest[4], sortLargest[3]);
    }
}

Answer 4

Implementación javascript simple.

function Node (value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right; 
}

function second (node, prev, wentLeft) {
    if (node.right) {
        return second(node.right, node, wentLeft);
    } else if (node.left) {
        return second(node.left, node, true);
    } else {
        if (wentLeft) return node.value;
        return prev.value;
    }
}
second(root);

Answer 5

La idea es ir todo el camino a la derecha hasta que no haya nada a la derecha. Si hay una izquierda, tómela y luego diríjase hacia la derecha. Si tomaste una izquierda, la respuesta es el último nodo encontrado. De lo contrario, la respuesta es el segundo último nodo que encontró.

Aquí hay una solución recursiva en Java:

public TreeNode getSecondLargest(TreeNode root) {
    if(root == null || (root.left == null && root.right == null))
        throw new IllegalArgumentException("The tree must have at least two nodes");
    return helper(root, null, false);
}

private TreeNode helper(TreeNode root, TreeNode parent, boolean wentLeft) {
    if(root.right != null) return helper(root.right, root, wentLeft);
    if(root.left != null && !wentLeft) return helper(root.left, root, true);

    if(wentLeft) return root;
    else return parent;
}

La complejidad del tiempo es O (lg n).

Answer 6

Lo haría pasando por el árbol del elemento más grande al más pequeño y devolviendo el valor cuando se alcance la posición solicitada. Implementé una tarea similar para el segundo mayor valor.

void BTree::findSecondLargestValueUtil(Node* r, int &c, int &v)
{
    if(r->right) {
        this->findSecondLargestValueUtil(r->right, c, v);
    }

    c++;

    if(c==2) {
        v = r->value;
        return;
    }

    if(r->left) {
        this->findSecondLargestValueUtil(r->left, c, v);
    }
}


int BTree::findSecondLargestValue()
{
    int c = 0;
    int v = -1;

    this->findSecondLargestValueUtil(this->root, c, v);

    return v;
}

Answer 7

No eso está mal. Considere este BST:

        137
       /
      42
       /
        99

Aquí, el valor segundo a máximo es el elemento secundario más a la derecha del elemento secundario izquierdo del valor máximo. Será necesario actualizar su algoritmo para que verifique el padre del valor máximo, o el subchild más a la derecha del hijo izquierdo del máximo.

Además, tenga en cuenta que el máximo no es necesariamente el nodo de hoja más a la derecha, es el nodo en la parte inferior de la columna derecha del árbol. Arriba, 137 no es una hoja.

¡Espero que esto ayude!

Answer 8

Recuerde que puede hacer una lista de los nodos de un BST en orden inverso haciendo un recorrido de orden modificado donde primero explora el subárbol correcto. Esto conduce a un algoritmo simple:

Node rightmost = findRightmostNode(root)
if (rightmost.left != null) {
    return findRightmostNode(rightmost.left)
else{
    return rightmost.parent
}

Devolvería nulo si el árbol tuviera un solo elemento.

Answer 9

Un enfoque iterativo mucho más fácil con la complejidad del tiempo O (logN) y la complejidad del espacio O (1)

public static void main(String[] args) {    
        BinaryTreeNode result=isBinarySearchTree.secondLargest(rootNode);

            System.out.println(result.data);
        }

        private BinaryTreeNode secondLargest(BinaryTreeNode node) {

            BinaryTreeNode prevNode=null; //2nd largest Element
            BinaryTreeNode currNode=node;
            if(null == currNode)
                return prevNode;

            while(currNode.right != null){
                prevNode=currNode;
                currNode=currNode.right;
            }
            if(currNode.left != null){
                currNode=currNode.left;
                while(currNode.right != null){
                    currNode=currNode.right;
                }
                prevNode=currNode;
            }

            return prevNode;

        }

Answer 10

Una forma muy intuitiva de pensar esto es considerando los siguientes dos casos. Deje el segundo nodo más grande como S, y el nodo más grande como L.

i) S se inserta en la BST "antes" que en L. ii) S se inserta en la BST "más tarde" que en L.

Para el primer caso, es obvio que L es el hijo correcto de S. Se debe a que cualquier nodo, excepto L, es más pequeño que S, por lo tanto, no se colocará en el lado derecho de S. Por lo tanto, cuando se coloca L, Será el hijo adecuado de S.

Para el segundo caso, en el momento en que se inserta S, L será el nodo más a la derecha en la BST. Obviamente, L no tendría un hijo adecuado porque es el más grande. Sin embargo, L podría tener su propio subárbol izquierdo. Cuando se inserta S, S seguirá el "camino correcto" hasta que se encuentre con L y luego gire a la izquierda para ir al subárbol izquierdo de L. Aquí, sabemos que todos los nodos en el subárbol izquierdo de L son más pequeños que S, por lo que S Será el nodo más a la derecha en el subárbol.

Answer 11

Una variante transversal:

   public Tree GetSecondMax(Tree root)
    {
        Tree parentOfMax = null;

        var maxNode = GetMaxNode(root, ref parentOfMax);

        if (maxNode == root || maxnode.left != null)
        {
            // if maximum node is root or have left subtree, then return maximum from left subtree
            return GetMaxNode(maxnode.left, ref parentOfMax);
        }

        // if maximum node is not root, then return parent of maximum node
        return parentOfMax;
    }

    private Tree GetMaxNode(Tree root, ref Tree previousNode)
    {
        if (root == null || root.right == null)
        {
            // The most right element have reached
            return root;
        }

        // we was there
        previousNode = root;

        return GetMaxNode(root.right, ref previousNode);
    }

Answer 12

int getSecondLargest(Node root){
    if(root==null)
        return 0;
    Node curr=root;
    Node prev=root;
    //Go to the largest node
    while(curr.right != null){
        prev = curr;
        curr= curr.right;
    }
    //If largest Node has left child, Then largest element of tree with its root as largest.left will be the second largest number.
    if(curr.left == null)
        return prev.data;
    else
        return findLargest(curr.left);
}

int findLargest(Node root){
    // No need toi check for null condition as in getSecondLargest method, its already done.
    Node curr=root;
    //To find largest just keep on going to right child till leaf is encountered.
    while(curr.right != null){
        curr = curr.right;
    }
    return curr.data;
}

Answer 13

int getmax(node *root)
{
    if(root->right == NULL)
    {
        return root->d;
    }
    return getmax(root->right);
}


int secondmax(node *root)
{
    if(root == NULL)
    {
        return -1;
    }

    if(root->right == NULL && root->left != NULL)
    {
        return getmax(root->left);
    }

    if(root->right != NULL)
    {
        if(root->right->right == NULL && root->right->left == NULL)
        {
            return root->d;
        }
    }

    return secondmax(root->right);
}

Answer 14

public static int findSecondLargestValueInBST(Node root)
    {
        int secondMax;
        Node pre = root;
        Node cur = root;
        while (cur.Right != null)
        {
            pre = cur;
            cur = cur.Right;
        }
        if (cur.Left != null)
        {
            cur = cur.Left;
            while (cur.Right != null)
                cur = cur.Right;
            secondMax = cur.Value;
        }
        else
        {
            if (cur == root && pre == root)
                //Only one node in BST
                secondMax = int.MinValue;
            else
                secondMax = pre.Value;
        }
        return secondMax;
    }