Genere dos BST de la array dada de modo que la altura máxima entre ellos sea mínima

Dada una array de n enteros donde n es mayor que 1 , la tarea es crear dos árboles de búsqueda binarios a partir de la array dada (en cualquier orden) de modo que la altura máxima entre los dos árboles sea la mínima posible e imprimir la altura máxima.
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, 4, 6} 
Salida: 1 
 

Entrada: arr[] = { 74, 25, 23, 1, 65, 2, 8, 99 } 
Salida: 2 
 

Enfoque: El objetivo es minimizar la altura del árbol de búsqueda binaria de altura máxima y para hacerlo necesitamos dividir los elementos de la array en partes iguales entre ambos árboles. Y como el orden no importa, podemos elegir fácilmente cualquier elemento para el primer o segundo árbol binario. Ahora, para minimizar la altura de los dos árboles, los árboles tendrán que estar casi completos y tan iguales en altura como sea posible. Y la altura máxima (minimizada) será log(n/2) o log(n/2 + 1).
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the log()
int cal_log(int n)
{
    int ans = 0;
 
    while (n) {
        n /= 2;
        ans++;
    }
 
    return ans;
}
 
// Function to return the maximum
// height of the tree
int maximumHeight(int n, int arr[])
{
    int level = cal_log(n / 2 + n % 2);
    return (level - 1);
}
 
// Driven code
int main()
{
    int arr[] = { 1, 2, 3, 4, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maximumHeight(n, arr);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
// Function to calculate the log()
static int cal_log(int n)
{
    int ans = 0;
 
    while (n > 0)
    {
        n /= 2;
        ans++;
    }
 
    return ans;
}
 
// Function to return the maximum
// height of the tree
static int maximumHeight(int n, int arr[])
{
    int level = cal_log(n / 2 + n % 2);
    return (level - 1);
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = { 1, 2, 3, 4, 6 };
    int n =arr.length;
    System.out.print( maximumHeight(n, arr));
}
}
 
// This code is contributed by anuj_67..

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to calculate the log()
static int cal_log(int n)
{
    int ans = 0;
 
    while (n > 0)
    {
        n /= 2;
        ans++;
    }
 
    return ans;
}
 
// Function to return the maximum
// height of the tree
static int maximumHeight(int n, int []arr)
{
    int level = cal_log(n / 2 + n % 2);
    return (level - 1);
}
 
// Driver code
public static void Main ()
{
    int []arr = { 1, 2, 3, 4, 6 };
    int n =arr.Length;
    Console.WriteLine( maximumHeight(n, arr));
}
}
 
// This code is contributed by anuj_67..

# Python implementation of the approach
 
# Function to calculate the log()
def cal_log(n):
    ans = 0;
 
    while (n):
        n //= 2;
        ans+=1;
 
 
    return ans;
 
 
# Function to return the maximum
# height of the tree
def maximumHeight(n, arr):
    level = cal_log(n // 2 + n % 2);
    return (level - 1);
 
 
# Driver code
arr = [ 1, 2, 3, 4, 6 ];
n = len(arr);
print(maximumHeight(n, arr));
 
# This code is contributed by Princi Singh

<script>
 
// Javascript implementation of the approach
 
// Function to calculate the log()
function cal_log(n)
{
    var ans = 0;
 
    while (n) {
        n = parseInt(n/2);
        ans++;
    }
 
    return ans;
}
 
// Function to return the maximum
// height of the tree
function maximumHeight(n, arr)
{
    var level = cal_log(parseInt(n / 2) + n % 2);
    return (level - 1);
}
 
// Driven code
var arr = [ 1, 2, 3, 4, 6 ];
var n = arr.length;
document.write( maximumHeight(n, arr));
 
</script>

1

Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(1)