Imprima la ruta desde un Node hasta la raíz del árbol binario completo dado

Dado un número entero N , la tarea es encontrar la ruta desde el ^Node N a la raíz de un árbol binario de la siguiente forma:

• El árbol binario es un árbol binario completo hasta el nivel del ^Node N.
• Los Nodes se numeran del 1 al N , comenzando desde la raíz como 1 .
• La estructura del Árbol es la siguiente: 
   

               1
           /       \
          2         3
       /    \    /   \
      4     5    6    7
      ................
   /    \ ............
 N - 1  N ............

Ejemplos:

Entrada: N = 7
Salida: 7 3 1
Explicación: La ruta desde el Node 7 hasta la raíz es 7 -> 3 -> 1.

Entrada: N = 11
Salida: 11 5 2 1
Explicación: La ruta desde el Node 11 hasta la raíz es 11 -> 5 -> 2 -> 1.

Enfoque ingenuo: el enfoque más simple para resolver el problema es realizar DFS desde el Node dado hasta que se encuentre el Node raíz e imprimir la ruta.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la estructura del árbol binario dado. Se puede observar que para todo N , su Node padre será N/2 . Por lo tanto, imprima repetidamente el valor actual de N y actualice N a N / 2 hasta que N sea igual a 1 , es decir, se alcance el Node raíz. 

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

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to print the path
// from node to root
void path_to_root(int node)
{
    // Iterate until root is reached
    while (node >= 1) {
 
        // Print the value of
        // the current node
        cout << node << ' ';
 
        // Move to parent of
        // the current node
        node /= 2;
    }
}
 
// Driver Code
int main()
{
    int N = 7;
    path_to_root(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
  
class GFG{
 
// Function to print the path
// from node to root
static void path_to_root(int node)
{
     
    // Iterate until root is reached
    while (node >= 1)
    {
         
        // Print the value of
        // the current node
        System.out.print(node + " ");
 
        // Move to parent of
        // the current node
        node /= 2;
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 7;
     
    path_to_root(N);
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 program for the above approach
 
# Function to print the path
# from node to root
def path_to_root(node):
     
    # Iterate until root is reached
    while (node >= 1):
 
        # Print the value of
        # the current node
        print(node, end = " ")
 
        # Move to parent of
        # the current node
        node //= 2
 
# Driver Code
if __name__ == '__main__':
 
    N = 7
 
    path_to_root(N)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG
{
 
// Function to print the path
// from node to root
static void path_to_root(int node)
{
     
    // Iterate until root is reached
    while (node >= 1)
    {
         
        // Print the value of
        // the current node
        Console.Write(node + " ");
 
        // Move to parent of
        // the current node
        node /= 2;
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 7;   
    path_to_root(N);
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
// Javascript program for the above approach
 
// Function to print the path
// from node to root
function path_to_root(node)
{
     
    // Iterate until root is reached
    while (node >= 1)
    {
         
        // Print the value of
        // the current node
        document.write(node + " ");
 
        // Move to parent of
        // the current node
        node = parseInt(node / 2, 10);
    }
}
 
// Driver code
let N = 7;
 
path_to_root(N);
 
// This code is contributed by divyeshrabadiya07
 
</script>

7 3 1

Complejidad de Tiempo: O(log ₂ (N))
Espacio Auxiliar: O(1)