Print path from a node to root of given Complete Binary Tree
Given an integer N, the task is to find the path from the Nth node to the root of a Binary Tree of the following form:
- The Binary Tree is a Complete Binary Tree up to the level of the Nth node.
- The nodes are numbered 1 to N, starting from the root as 1.
- The structure of the Tree is as follows:
1 / \ 2 3 / \ / \ 4 5 6 7 ................ / \ ............ N - 1 N ............
Examples:
Input: N = 7
Output: 7 3 1
Explanation: The path from the node 7 to root is 7 -> 3 -> 1.Input: N = 11
Output: 11 5 2 1
Explanation: The path from node 11 to root is 11 -> 5 -> 2 -> 1.
Naive Approach: The simplest approach to solve the problem is to perform DFS from the given node until the root node is encountered and print the path.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the structure of the given Binary Tree. It can be observed that for every N, its parent node will be N / 2. Therefore, repeatedly print the current value of N and update N to N / 2 until N is equal to 1, i.e. root node is reached.
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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
Time Complexity: O(log2(N))
Auxiliary Space: O(1)
Contact Us