Given a tree with N nodes where node 1 is the root, the task is to solve the queries of form {u, k} and find the parent that is k level above the node u.
Note: If the parent is not available then return -1.
Examples:
Input: N = 5 Q = 3, queries = {{4, 1}, {4, 2}, {4, 3}}
Example of the tree
Output: 3, 1, -1
Explanation: The node 4 is itself in the 3rd level. So there is no node which is 3 level above it.
Approach: The basic idea is as follows
For each store its parents and how much level it is above from that node in a 2D array.
Follow the below illustration how to build the array.
How to build the 2D array:
- We can use the concept of a sparse table.
- Simply we can store the parent of each node one level up then we can store parents at 2 level up, then 4 level up and recursively we can store the parents upto the root.
Lets say the 2D array is par[][] where par[i][j] will store 2i level up parent of node j. So for the example tree, the 0th row will look like the following.
Suppose we want to find the 2 level-up parent of 4, then, we know 1 level up to node 4 is node 3 and 1 level up to node 3 is node 1. So the distance between node 1 and 3 is 1 and node 3 and node 4 is 1. So the total distance between node 1 and 4 would be 2. So we can say that
x = par[i – 1][j]
par[i][j] = par[i-1][x]
We can take help of bits to calculate this efficiently as K can be represented as sum of powers of 2. Let’s say K = 11 so K = 1+2+8. We can simply do it like
- lets x = 1st parent of j
- let y = 2 level up parent of x
- let z = 8 level up parent of y
So our final answer would be z
Follow the steps mentioned below to implement the idea:
- Initially build the 2D array as shown above for all the nodes of the tree.
- This can be done using a single DFS.
- Then for each query, we can find the parent in O(log K) time using the above lookup.
Below is the implementation of the above approach.
C++
// C++ code to implement the idea#include <bits/stdc++.h>using namespace std;// Structure of a tree nodestruct Node { int val; Node *left, *right; Node(int x) { val = x; left = right = NULL; }};// Function to fill the 0th level parent of any nodevoid dfs(Node* cur, Node* parent, vector<vector<int> >& par){ if (cur == NULL) return; par[0][cur->val] = parent->val; dfs(cur->left, cur, par); dfs(cur->right, cur, par);}// Function to calculate k level up parent.int findKlevelup(int u, int k, vector<vector<int> >& par){ for (int i = 0; i < 19; i++) { if ((k >> i) & 1) u = par[i][u]; } return (u ? u : -1);}// Function to solve the provided queries and// find the respectie parentvoid solve(int n, int q, vector<vector<int> >& queries, Node* root){ vector<vector<int> > par(20, vector<int>(n, 0)); par[0][root->val] = 0; dfs(root->left, root, par); dfs(root->right, root, par); // Create the parent array for (int i = 1; i <= 18; i++) { for (int j = 1; j <= n; j++) par[i][j] = par[i - 1][par[i - 1][j]]; } // Loop to solve the queries for (int i = 0; i < q; i++) { int u, k; u = queries[i][0]; k = queries[i][1]; // Function to calculate for k level // up parent int ans = findKlevelup(u, k, par); cout << ans << " "; }}// Driver codeint main(){ int N = 5; int Q = 3; // Form the binary tree Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->right->left = new Node(4); root->right->right = new Node(5); vector<vector<int> > queries; queries = { { 4, 1 }, { 4, 2 }, { 4, 3 } }; // Function call solve(N, Q, queries, root); return 0;} |
Java
// Java code to implement the ideaclass GFG{ // Structure of a tree node static class Node { int val; Node left, right; Node(int x) { val = x; left = right = null; } }; // Function to fill the 0th level parent of any node static void dfs(Node cur, Node parent, int[][]par) { if (cur == null) return; par[0][cur.val] = parent.val; dfs(cur.left, cur, par); dfs(cur.right, cur, par); } // Function to calculate k level up parent. static int findKlevelup(int u, int k, int[][]par) { for (int i = 0; i < 19; i++) { if (((k >> i) & 1) > 0) u = par[i][u]; } return (u > 0 ? u : -1); } // Function to solve the provded queries and // find the respectie parent static void solve(int n, int q, int [][]queries, Node root) { int [][] par = new int[20][20]; par[0][root.val] = 0; dfs(root.left, root, par); dfs(root.right, root, par); // Create the parent array for (int i = 1; i <= 18; i++) { for (int j = 1; j <= n; j++) par[i][j] = par[i - 1][par[i - 1][j]]; } // Loop to solve the queries for (int i = 0; i < q; i++) { int u, k; u = queries[i][0]; k = queries[i][1]; // Function to calculate for k level // up parent int ans = findKlevelup(u, k, par); System.out.print(ans + " "); } } // Driver code public static void main(String args[]) { int N = 5; int Q = 3; // Form the binary tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.left = new Node(4); root.right.right = new Node(5); int [][] queries = { { 4, 1 }, { 4, 2 }, { 4, 3 } }; // Function call solve(N, Q, queries, root); }}// This code is contributed By Saurabh Jaiswal |
Python3
# Python code to implement the idea# Structure of a tree nodeclass Node: def __init__(self, x): self.left = None self.right = None self.val = x# Function to fill the 0th level parent of any node.def dfs(cur, parent, par): if(cur == None): return par[0][cur.val] = parent.val dfs(cur.left, cur, par) dfs(cur.right, cur, par)# Function to calculate k level up parent.def findKlevelup(u, k, par): for i in range(19): if(((k >> i) & 1) > 0): u = par[i][u] return u if u > 0 else -1# Function to solve the provided queries# and find the respective parentdef solve(n, q, queries, root): par = [[0 for x in range(20)] for y in range(20)] par[0][root.val] = 0 dfs(root.left, root, par) dfs(root.right, root, par) # create the parent array for i in range(1, 19): for j in range(1, n+1): par[i][j] = par[i-1][par[i-1][j]] # loop to solve the queries for i in range(q): u = queries[i][0] k = queries[i][1] # Function to calculate for k level up parent ans = findKlevelup(u, k, par) print(ans, end=" ")N, Q = 5, 3# Form the binary treeroot = Node(1)root.left = Node(2)root.right = Node(3)root.right.left = Node(4)root.right.right = Node(5)queries = [[4, 1], [4, 2], [4, 3]]# Function callsolve(N, Q, queries, root)# This code is contributed By lokesh. |
C#
// C# code to implement the ideausing System;public class GFG { // Structure of a tree node class Node { public int val; public Node left, right; public Node(int x) { val = x; left = right = null; } } // Function to fill the 0th level parent of any node static void dfs(Node cur, Node parent, int[, ] par) { if (cur == null) return; par[0, cur.val] = parent.val; dfs(cur.left, cur, par); dfs(cur.right, cur, par); } // Function to calculate k level up parent. static int findKlevelup(int u, int k, int[, ] par) { for (int i = 0; i < 19; i++) { if (((k >> i) & 1) > 0) u = par[i, u]; } return (u > 0 ? u : -1); } // Function to solve the provded queries and // find the respectie parent static void solve(int n, int q, int[, ] queries, Node root) { int[, ] par = new int[20, 20]; par[0, root.val] = 0; dfs(root.left, root, par); dfs(root.right, root, par); // Create the parent array for (int i = 1; i <= 18; i++) { for (int j = 1; j <= n; j++) par[i, j] = par[i - 1, par[i - 1, j]]; } // Loop to solve the queries for (int i = 0; i < q; i++) { int u, k; u = queries[i, 0]; k = queries[i, 1]; // Function to calculate for k level // up parent int ans = findKlevelup(u, k, par); Console.Write(ans + " "); } } static public void Main() { // Code int N = 5; int Q = 3; // Form the binary tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.left = new Node(4); root.right.right = new Node(5); int[, ] queries = { { 4, 1 }, { 4, 2 }, { 4, 3 } }; // Function call solve(N, Q, queries, root); }}// This code is contributed By lokeshmvs21. |
Javascript
// JavaScript code for the above approach // Structure of a tree node class Node { constructor(item) { this.val = item; this.left = this.right = null; } } // Function to fill the 0th level parent of any node function dfs(cur, parent, par) { if (cur == null) return; par[0][cur.val] = parent.val; dfs(cur.left, cur, par); dfs(cur.right, cur, par); } // Function to calculate k level up parent. function findKlevelup(u, k, par) { for (let i = 0; i < 19; i++) { if ((k >> i) & 1) u = par[i][u]; } return (u ? u : -1); } // Function to solve the provded queries and // find the respectie parent function solve(n, q, queries, root) { let par = new Array(20); for (let i = 0; i < par.length; i++) { par[i] = new Array(n).fill(0); } par[0][root.val] = 0; dfs(root.left, root, par); dfs(root.right, root, par); // Create the parent array for (let i = 1; i <= 18; i++) { for (let j = 1; j <= n; j++) par[i][j] = par[i - 1][par[i - 1][j]]; } // Loop to solve the queries for (let i = 0; i < q; i++) { let u, k; u = queries[i][0]; k = queries[i][1]; // Function to calculate for k level // up parent let ans = findKlevelup(u, k, par); console.log(ans + " "); } } // Driver code let N = 5; let Q = 3; // Form the binary tree let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.left = new Node(4); root.right.right = new Node(5); let queries; queries = [[4, 1], [4, 2], [4, 3]]; // Function call solve(N, Q, queries, root);// This code is contributed by Potta Lokesh |
Output
3 1 -1
Time Complexity: O(N+ Q*LogK)
Auxiliary Space: O(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!
Share your thoughts in the comments
