Given an integer N and an N-ary Tree of the following form:
- Every node is numbered sequentially, starting from 1, till the last level, which contains the node N.
- The nodes at every odd level contains 2 children and nodes at every even level contains 4 children.
The task is to print the path from the root node to the node N.
Examples:
Input: N = 14
Output: 1 2 5 14
Explanation: The path from node 1 to node 14 is 1 – > 2 – > 5 – > 14.Input: N = 11
Output: 1 3 11
Explanation: The path from node 1 to node 11 is 1 – > 3 – > 11.
Approach: Follow the steps below to solve the problem:
- Initialize an array to store the number of nodes present in each level of the Tree, i.e. {1, 2, 8, 16, 64, 128 ….} and store it.
- Calculate prefix sum of the array i.e. {1 3 11 27 91 219 …….}
- Find the index ind in the prefix sum array which exceeds or is equal to N using lower_bound(). Therefore, ind indicates the number of levels that need to be traversed to reach node N.
- Initialize a variable say, temp = N and an array path[] to store the nodes from root to N.
- Decrement ind until it is less than or equal to 1 and keep updating val = temp – prefix[ind – 1].
- Update temp = prefix[ind – 2] + (val + 1) / 2 if ind is odd.
- Otherwise, update temp = prefix[ind – 2] + (val + 3) / 4 if ind is even.
- Append temp into the path[] array.
- Finally, print the array, path[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;typedef long long ll;// Function to find the path// from root to Nvoid PrintPathNodes(ll N){ // Stores the number of // nodes at (i + 1)-th level vector<ll> arr; arr.push_back(1); // Stores the number of nodes ll k = 1; // Stores if the current // level is even or odd bool flag = true; while (k < N) { // If level is odd if (flag == true) { k *= 2; flag = false; } // If level is even else { k *= 4; flag = true; } // If level with // node N is reached if (k > N) { break; } // Push into vector arr.push_back(k); } ll len = arr.size(); vector<ll> prefix(len); prefix[0] = 1; // Compute prefix sums of count // of nodes in each level for (ll i = 1; i < len; ++i) { prefix[i] = arr[i] + prefix[i - 1]; } vector<ll>::iterator it = lower_bound(prefix.begin(), prefix.end(), N); // Stores the level in which // node N s present ll ind = it - prefix.begin(); ll temp = N; // Store path vector<int> path; path.push_back(N); while (ind > 1) { ll val = temp - prefix[ind - 1]; if (ind % 2 != 0) { temp = prefix[ind - 2] + (val + 1) / 2; } else { temp = prefix[ind - 2] + (val + 3) / 4; } --ind; // Insert temp into path path.push_back(temp); } if (N != 1) path.push_back(1); // Print path for (int i = path.size() - 1; i >= 0; i--) { cout << path[i] << " "; }}// Driver Codeint main(){ ll N = 14; // Function Call PrintPathNodes(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main { // Function to find the path // from root to N static void PrintPathNodes(long N) { // Stores the number of // nodes at (i + 1)-th level ArrayList<Long> arr = new ArrayList<>(); arr.add((long)1); // Stores the number of nodes long k = 1; // Stores if the current // level is even or odd boolean flag = true; while (k < N) { // If level is odd if (flag == true) { k *= 2; flag = false; } // If level is even else { k *= 4; flag = true; } // If level with // node N is reached if (k > N) { break; } // Push into array arr.add(k); } long len = arr.size(); ArrayList<Long> prefix = new ArrayList<>(); prefix.add((long)1); // Compute prefix sums of count // of nodes in each level for (long i = 1; i < len; ++i) { prefix.add(arr.get((int)i) + prefix.get((int)i - 1)); } int ind = Collections.binarySearch(prefix, N); // Stores the level in which // node N s present if (ind < 0) { ind = -ind - 1; } long temp = N; // Store path ArrayList<Long> path = new ArrayList<>(); path.add(N); while (ind > 1) { long val = temp - prefix.get((int)ind - 1); if (ind % 2 != 0) { temp = prefix.get((int)ind - 2) + (val + 1) / 2; } else { temp = prefix.get((int)ind - 2) + (val + 3) / 4; } --ind; // Insert temp into path path.add(temp); } if (N != 1) path.add((long)1); // Print path for (int i = path.size() - 1; i >= 0; i--) { System.out.print(path.get(i) + " "); } } // Driver Code public static void main(String[] args) { long N = 14; // Function Call PrintPathNodes(N); }}// This code is contributed by princekumaras |
Python3
# Python3 program for the above approachfrom bisect import bisect_left# Function to find the path# from root to Ndef PrintPathNodes(N): # Stores the number of # nodes at (i + 1)-th level arr = [] arr.append(1) # Stores the number of nodes k = 1 # Stores if the current # level is even or odd flag = True while (k < N): # If level is odd if (flag == True): k *= 2 flag = False # If level is even else: k *= 4 flag = True # If level with # node N is reached if (k > N): break # Push into vector arr.append(k) lenn = len(arr) prefix = [0]*(lenn) prefix[0] = 1 # Compute prefix sums of count # of nodes in each level for i in range(1,lenn): prefix[i] = arr[i] + prefix[i - 1] it = bisect_left(prefix, N) # Stores the level in which # node N s present ind = it temp = N # Store path path = [] path.append(N) while (ind > 1): val = temp - prefix[ind - 1] if (ind % 2 != 0): temp = prefix[ind - 2] + (val + 1) // 2 else: temp = prefix[ind - 2] + (val + 3) // 4 ind -= 1 # Insert temp into path path.append(temp) if (N != 1): path.append(1) # Print path for i in range(len(path)-1, -1, -1): print(path[i], end=" ")# Driver Codeif __name__ == '__main__': N = 14 # Function Call PrintPathNodes(N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the path // from root to N static void PrintPathNodes(long N) { // Stores the number of // nodes at (i + 1)-th level List<long> arr = new List<long>(); arr.Add((long)1); // Stores the number of nodes long k = 1; // Stores if the current // level is even or odd bool flag = true; while (k < N) { // If level is odd if (flag == true) { k *= 2; flag = false; } // If level is even else { k *= 4; flag = true; } // If level with // node N is reached if (k > N) { break; } // Push into array arr.Add(k); } long len = arr.Count; List<long> prefix = new List<long>(); prefix.Add((long)1); // Compute prefix sums of count // of nodes in each level for (long i = 1; i < len; ++i) { prefix.Add(arr[(int)i] + prefix[(int)i - 1]); } int ind = prefix.BinarySearch(N); // Stores the level in which // node N s present if (ind < 0) { ind = -ind - 1; } long temp = N; // Store path List<long> path = new List<long>(); path.Add(N); while (ind > 1) { long val = temp - prefix[(int)ind - 1]; if (ind % 2 != 0) { temp = prefix[(int)ind - 2] + (val + 1) / 2; } else { temp = prefix[(int)ind - 2] + (val + 3) / 4; } --ind; // Insert temp into path path.Add(temp); } if (N != 1) path.Add((long)1); // Print path for (int i = path.Count - 1; i >= 0; i--) { Console.Write(path[i] + " "); } } // Driver Code public static void Main(string[] args) { long N = 14; // Function Call PrintPathNodes(N); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program for the above approachfunction bisect_left(a, x, lo = 0, hi = a.length) { while (lo < hi) { let mid = Math.floor((lo + hi) / 2); if (a[mid] < x) { lo = mid + 1; } else { hi = mid; } } return lo;}// Function to find the path// from root to Nfunction PrintPathNodes(N) { // Stores the number of // nodes at (i + 1)-th level let arr = []; arr.push(1); // Stores the number of nodes let k = 1; // Stores if the current // level is even or odd let flag = true; while (k < N) { // If level is odd if (flag === true) { k *= 2; flag = false; } // If level is even else { k *= 4; flag = true; } // If level with // node N is reached if (k > N) { break; } // Push into array arr.push(k); } let lenn = arr.length; let prefix = new Array(lenn).fill(0); prefix[0] = 1; // Compute prefix sums of count // of nodes in each level for (let i = 1; i < lenn; i++) { prefix[i] = arr[i] + prefix[i - 1]; } let it = bisect_left(prefix, N); // Stores the level in which // node N s present let ind = it; let temp = N; // Store path let path = []; path.push(N); while (ind > 1) { let val = temp - prefix[ind - 1]; if (ind % 2 !== 0) { temp = prefix[ind - 2] + Math.floor((val + 1) / 2); } else { temp = prefix[ind - 2] + Math.floor((val + 3) / 4); } ind -= 1; // Insert temp into path path.push(temp); } if (N !== 1) { path.push(1); } // Print path for (let i = path.length - 1; i >= 0; i--) { process.stdout.write(path[i] + " "); }}// Driver Codelet N = 14;// Function CallPrintPathNodes(N);// This code is contributed by phasing17 |
Output:
1 2 5 14
Time Complexity: O(log(N))
Auxiliary Space: O(log(N))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
