Encuentre el Node más a la izquierda y más a la derecha de BST a partir de su recorrido de preorden dado

Dada una secuencia de preorden del árbol de búsqueda binaria de N Nodes. La tarea es encontrar sus Nodes más a la izquierda y más a la derecha.

Ejemplos: 

Input : N = 5, preorder[]={ 3, 2, 1, 5, 4 }
Output : Leftmost = 1, Rightmost = 5
The BST constructed from this 
preorder sequence would be:
         3
       /   \
      2     5
     /     /
    1     4
Leftmost Node of this tree is equal to 1
Rightmost Node of this tree is equal to 5

Input : N = 3 preorder[]={ 2, 1, 3}
Output : Leftmost = 1, Rightmost = 3 

Enfoque ingenuo: 
construya BST a partir de la secuencia de preorden dada. Consulte esta publicación para comprender el código para construir bst a partir de un pedido anticipado determinado. Después de construir el BST, encuentre el Node más a la izquierda y más a la derecha atravesando desde la raíz hasta el Node más a la izquierda y atravesando desde la raíz hasta el Node más a la derecha.
Complejidad temporal: O(N) 
Complejidad espacial: O(N)

Enfoque eficiente: 
en lugar de construir el árbol, utilice la propiedad de BST. El Node más a la izquierda en BST siempre tiene el valor más pequeño y el Node más a la derecha en BST siempre tiene el valor más grande. 
Entonces, de la array dada solo necesitamos encontrar el valor mínimo para el Node más a la izquierda y el valor máximo para el Node más a la derecha.
 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to find leftmost and
// rightmost node from given preorder sequence
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the leftmost and
// rightmost nodes of the BST whose
// preorder traversal is given
void LeftRightNode(int preorder[], int n)
{
    // Variables for finding minimum
    // and maximum values of the array
    int min = INT_MAX, max = INT_MIN;
 
    for (int i = 0; i < n; i++) {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
    
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
 
    // Print the values
    cout << "Leftmost node is " << min << "\n";
    cout << "Rightmost node is " << max;
}
 
// Driver Code
int main()
{
    int preorder[] = { 3, 2, 1, 5, 4 };
    int n = 5;
 
    LeftRightNode(preorder, n);
    return 0;
}

// Java program to find leftmost and
// rightmost node from given preorder sequence
class GFG
{
 
// Function to return the leftmost and
// rightmost nodes of the BST whose
// preorder traversal is given
static void LeftRightNode(int preorder[], int n)
{
    // Variables for finding minimum
    // and maximum values of the array
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
 
    for (int i = 0; i < n; i++)
    {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
     
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
    // Print the values
    System.out.println("Leftmost node is " + min);
    System.out.println("Rightmost node is " + max);
}
 
// Driver Code
public static void main(String[] args)
{
        int preorder[] = { 3, 2, 1, 5, 4 };
        int n = 5;
        LeftRightNode(preorder, n);
 
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find leftmost and
# rightmost node from given preorder sequence
 
# Function to return the leftmost and
# rightmost nodes of the BST whose
# preorder traversal is given
def LeftRightNode(preorder, n):
    # Variables for finding minimum
    # and maximum values of the array
    min = 10**9
    max = -10**9
 
    for i in range(n):
         
        # Update the minimum
        if (min > preorder[i]):
            min = preorder[i]
     
        # Update the maximum
        if (max < preorder[i]):
            max = preorder[i]
 
    # Print the values
    print("Leftmost node is ",min)
    print("Rightmost node is ",max)
 
# Driver Code
 
preorder = [3, 2, 1, 5, 4]
n =len(preorder)
 
LeftRightNode(preorder, n)
 
# This code is contributed by mohit kumar 29

// C# program to find leftmost and
// rightmost node from given preorder sequence
using System;
     
class GFG
{
 
// Function to return the leftmost and
// rightmost nodes of the BST whose
// preorder traversal is given
static void LeftRightNode(int []preorder, int n)
{
    // Variables for finding minimum
    // and maximum values of the array
    int min = int.MaxValue, max = int.MinValue;
 
    for (int i = 0; i < n; i++)
    {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
     
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
    // Print the values
    Console.WriteLine("Leftmost node is " + min);
    Console.WriteLine("Rightmost node is " + max);
}
 
// Driver Code
public static void Main(String[] args)
{
        int []preorder = { 3, 2, 1, 5, 4 };
        int n = 5;
        LeftRightNode(preorder, n);
 
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to find leftmost and
// rightmost node from given preorder sequence
 
// Function to return the leftmost and
// rightmost nodes of the BST whose
// preorder traversal is given
function LeftRightNode(preorder, n)
{
    // Variables for finding minimum
    // and maximum values of the array
    var min = 1000000000, max = -1000000000;
 
    for (var i = 0; i < n; i++) {
         
        // Update the minimum
        if (min > preorder[i])
            min = preorder[i];
    
        // Update the maximum
        if (max < preorder[i])
            max = preorder[i];
    }
 
    // Print the values
    document.write( "Leftmost node is " + min + "<br>");
    document.write( "Rightmost node is " + max);
}
 
// Driver Code
var preorder = [3, 2, 1, 5, 4];
var n = 5;
LeftRightNode(preorder, n);
 
</script>

Leftmost node is 1
Rightmost node is 5

Complejidad de tiempo: O(N) 
Complejidad de espacio: O(1)