Imprima la ruta desde la raíz a todos los Nodes en un árbol binario completo

Dado un número N , que es el número total de Nodes en un árbol binario completo donde los Nodes son números del 1 al N secuencialmente por niveles. La tarea es escribir un programa para imprimir rutas desde la raíz a todos los Nodes en el árbol binario completo.
Para N = 3, el árbol será: 
 

     1
  /     \
2        3 

Para N = 7, el árbol será: 
 

       1
    /     \
   2        3 
 /   \    /  \ 
4    5    6   7

Ejemplos: 
 

Input : 7  
Output : 
1 
1 2 
1 2 4 
1 2 5 
1 3 
1 3 6 
1 3 7 

Input : 4 
Output :
1 
1 2 
1 2 4 
1 3 

Explicación : – Dado que el árbol dado es un árbol binario completo. Para cada Node  , podemos calcular su hijo izquierdo como 2*i y su hijo derecho como 2*i + 1 .
La idea es utilizar un enfoque de retroceso para imprimir todas las rutas. Mantenga un vector para almacenar rutas, inicialmente presione el Node raíz 1 hacia él, y antes de presionar los elementos secundarios izquierdo y derecho, imprima la ruta actual almacenada en él y luego llame a la función para los elementos secundarios izquierdo y derecho también. 
A continuación se muestra la implementación completa del enfoque anterior:
 

// C++ program to print path from root to all
// nodes in a complete binary tree.
 
#include <iostream>
#include <vector>
using namespace std;
 
// Function to print path of all the nodes
// nth node represent as given node
// kth node represents as left and right node
void printPath(vector<int> res, int nThNode, int kThNode)
{
    // base condition
    // if kth node value is greater
    // then nth node then its means
    // kth node is not valid so
    // we not store it into the res
    // simply we just return
    if (kThNode > nThNode)
        return;
 
    // Storing node into res
    res.push_back(kThNode);
 
    // Print the path from root to node
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    cout << "\n";
 
    // store left path of a tree
    // So for left we will go node(kThNode*2)
    printPath(res, nThNode, kThNode * 2);
 
    // right path of a tree
    // and for right we will go node(kThNode*2+1)
    printPath(res, nThNode, kThNode * 2 + 1);
}
 
// Function to print path from root to all of the nodes
void printPathToCoverAllNodeUtil(int nThNode)
{
    // res is for store the path
    // from root to particulate node
    vector<int> res;
 
    // Print path from root to all node.
    // third argument 1 because of we have
    // to consider root node is 1
    printPath(res, nThNode, 1);
}
 
// Driver Code
int main()
{
    // Given Node
    int nThNode = 7;
 
    // Print path from root to all node.
    printPathToCoverAllNodeUtil(nThNode);
 
    return 0;
}

// Java program to print path from root to all
// nodes in a complete binary tree.
import java.util.*;
 
class GFG
{
 
// Function to print path of all the nodes
// nth node represent as given node
// kth node represents as left and right node
static void printPath(Vector<Integer> res,
                    int nThNode, int kThNode)
{
    // base condition
    // if kth node value is greater
    // then nth node then its means
    // kth node is not valid so
    // we not store it into the res
    // simply we just return
    if (kThNode > nThNode)
        return;
 
    // Storing node into res
    res.add(kThNode);
 
    // Print the path from root to node
    for (int i = 0; i < res.size(); i++)
        System.out.print( res.get(i) + " ");
    System.out.print( "\n");
 
    // store left path of a tree
    // So for left we will go node(kThNode*2)
    printPath(res, nThNode, kThNode * 2);
 
    // right path of a tree
    // and for right we will go node(kThNode*2+1)
    printPath(res, nThNode, kThNode * 2 + 1);
     
    res.remove(res.size()-1);
}
 
// Function to print path from root to all of the nodes
static void printPathToCoverAllNodeUtil(int nThNode)
{
    // res is for store the path
    // from root to particulate node
    Vector<Integer> res=new Vector<Integer>();
 
    // Print path from root to all node.
    // third argument 1 because of we have
    // to consider root node is 1
    printPath(res, nThNode, 1);
}
 
// Driver Code
public static void main(String args[])
{
    // Given Node
    int nThNode = 7;
 
    // Print path from root to all node.
    printPathToCoverAllNodeUtil(nThNode);
}
}
 
// This code is contributed by Arnab Kundu

# Python3 program to print path from root
# to all nodes in a complete binary tree.
 
# Function to print path of all the nodes
# nth node represent as given node kth
# node represents as left and right node
def printPath(res, nThNode, kThNode):
 
    # base condition
    # if kth node value is greater
    # then nth node then its means
    # kth node is not valid so
    # we not store it into the res
    # simply we just return
    if kThNode > nThNode:
        return
 
    # Storing node into res
    res.append(kThNode)
 
    # Print the path from root to node
    for i in range(0, len(res)):
        print(res[i], end = " ")
    print()
 
    # store left path of a tree
    # So for left we will go node(kThNode*2)
    printPath(res[:], nThNode, kThNode * 2)
 
    # right path of a tree
    # and for right we will go node(kThNode*2+1)
    printPath(res[:], nThNode, kThNode * 2 + 1)
 
# Function to print path from root
# to all of the nodes
def printPathToCoverAllNodeUtil(nThNode):
 
    # res is for store the path
    # from root to particulate node
    res = []
 
    # Print path from root to all node.
    # third argument 1 because of we have
    # to consider root node is 1
    printPath(res, nThNode, 1)
 
# Driver Code
if __name__ == "__main__":
 
    # Given Node
    nThNode = 7
 
    # Print path from root to all node.
    printPathToCoverAllNodeUtil(nThNode)
 
# This code is contributed by Rituraj Jain

// C# program to print path from root to all
// nodes in a complete binary tree.
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to print path of all the nodes
// nth node represent as given node
// kth node represents as left and right node
static void printPath(List<int> res,
                    int nThNode, int kThNode)
{
    // base condition
    // if kth node value is greater
    // then nth node then its means
    // kth node is not valid so
    // we not store it into the res
    // simply we just return
    if (kThNode > nThNode)
        return;
 
    // Storing node into res
    res.Add(kThNode);
 
    // Print the path from root to node
    for (int i = 0; i < res.Count; i++)
        Console.Write( res[i] + " ");
    Console.Write( "\n");
 
    // store left path of a tree
    // So for left we will go node(kThNode*2)
    printPath(res, nThNode, kThNode * 2);
 
    // right path of a tree
    // and for right we will go node(kThNode*2+1)
    printPath(res, nThNode, kThNode * 2 + 1);
     
    res.RemoveAt(res.Count-1);
}
 
// Function to print path from root to all of the nodes
static void printPathToCoverAllNodeUtil(int nThNode)
{
    // res is for store the path
    // from root to particulate node
    List<int> res=new List<int>();
 
    // Print path from root to all node.
    // third argument 1 because of we have
    // to consider root node is 1
    printPath(res, nThNode, 1);
}
 
// Driver Code
public static void Main(String []args)
{
    // Given Node
    int nThNode = 7;
 
    // Print path from root to all node.
    printPathToCoverAllNodeUtil(nThNode);
}
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to print path from root to all
// nodes in a complete binary tree.
 
// Function to print path of all the nodes
// nth node represent as given node
// kth node represents as left and right node
function printPath($res, $nThNode, $kThNode)
{
    // base condition
    // if kth node value is greater
    // then nth node then its means
    // kth node is not valid so
    // we not store it into the res
    // simply we just return
    if ($kThNode > $nThNode)
        return;
 
    // Storing node into res
    array_push($res, $kThNode);
 
    // Print the path from root to node
    for ($i = 0; $i < count($res); $i++)
        echo $res[$i] . " ";
    echo "\n";
 
    // store left path of a tree
    // So for left we will go node(kThNode*2)
    printPath($res, $nThNode, $kThNode * 2);
 
    // right path of a tree
    // and for right we will go node(kThNode*2+1)
    printPath($res, $nThNode, $kThNode * 2 + 1);
}
 
// Function to print path
// from root to all of the nodes
function printPathToCoverAllNodeUtil($nThNode)
{
    // res is for store the path
    // from root to particulate node
    $res = array();
 
    // Print path from root to all node.
    // third argument 1 because of we have
    // to consider root node is 1
    printPath($res, $nThNode, 1);
}
 
// Driver Code
 
// Given Node
$nThNode = 7;
 
// Print path from root to all node.
printPathToCoverAllNodeUtil($nThNode);
 
// This code is contributed by mits
?>

<script>
 
// JavaScript program to print path from root to all
// nodes in a complete binary tree.
 
// Function to print path of all the nodes
// nth node represent as given node
// kth node represents as left and right node
function printPath(res, nThNode, kThNode)
{
    // base condition
    // if kth node value is greater
    // then nth node then its means
    // kth node is not valid so
    // we not store it into the res
    // simply we just return
    if (kThNode > nThNode)
        return;
 
    // Storing node into res
    res.push(kThNode);
 
    // Print the path from root to node
    for (var i = 0; i < res.length; i++)
        document.write( res[i] + " ");
    document.write( "<br>");
 
    // store left path of a tree
    // So for left we will go node(kThNode*2)
    printPath(res, nThNode, kThNode * 2);
 
    // right path of a tree
    // and for right we will go node(kThNode*2+1)
    printPath(res, nThNode, kThNode * 2 + 1);
 
    res.pop()
}
 
// Function to print path from root to all of the nodes
function printPathToCoverAllNodeUtil( nThNode)
{
    // res is for store the path
    // from root to particulate node
    var res = [];
 
    // Print path from root to all node.
    // third argument 1 because of we have
    // to consider root node is 1
    printPath(res, nThNode, 1);
}
 
// Driver Code
 
// Given Node
var nThNode = 7;
 
// Print path from root to all node.
printPathToCoverAllNodeUtil(nThNode);
 
 
</script>

1 
1 2 
1 2 4 
1 2 5 
1 3 
1 3 6 
1 3 7