Traversal of tree with k jumps allowed between nodes of same height
There is a tree with N nodes and node 1 is the root node. Each node of the tree can contain fruit or not. Initially, you are at the root node and start climbing on the tree. You can jump from a node to any node at the same level(i.e. the height of nodes from the root are same), During climbing from root node you can only make maximum K jumps. (K < 20) Now you have to climb on the tree (from root node-> any leaf node) in such a way so that you can collect maximum no of fruits.
Example :
Input Tree :
Number of Nodes N = 12
Number of jumps allowed : 2
Edges:
1 2
1 3
2 4
2 5
5 9
9 10
9 11
11 12
3 7
7 6
7 8
no of node having fruit(nf) : 8
Nodes Containing Fruits(lvn) : 2 4 5 7 8 9 11 12
Output: 7
Tree for above testcase :
Explanation:
Approach: The idea is to use DFS to create a Height Adjacency List of the Nodes and to store the parents. Then use another dfs to compute the maximum no of special nodes that can be reached using the following dp state:
dp[current_node][j] = max( max{ dp[child_i][j], for all children of current_node },
max{ dp[node_at_same_height_i][j - 1],
for all nodes at same height as current_node} )
Thus, dp[Root_Node][Total_no_of_Jumps] gives the answer to the problem.
Below is the implementation of the above approach :
CPP
// Program to demonstrate tree traversal with// ability to jump between nodes of same height#include <bits/stdc++.h>using namespace std;#define N 1000vector<int> H[N];// Arrays declarationint Fruit[N];int Parent[N];int dp[N][20];// Function for DFSvoid dfs1(vector<int> tree[], int s, int p, int h){ Parent[s] = p; int i; H[h].push_back(s); for (i = 0; i < tree[s].size(); i++) { int v = tree[s][i]; if (v != p) dfs1(tree, v, s, h + 1); }}// Function for DFSint dfs2(vector<int> tree[], int s, int p, int h, int j){ int i; int ans = 0; if (dp[s][j] != -1) return dp[s][j]; // jump if (j > 0) { for (i = 0; i < H[h].size(); i++) { int v = H[h][i]; if (v != s) ans = max(ans, dfs2(tree, v, Parent[v], h, j - 1)); } } // climb for (i = 0; i < tree[s].size(); i++) { int v = tree[s][i]; if (v != p) ans = max(ans, dfs2(tree, v, s, h + 1, j)); } if (Fruit[s] == 1) ans++; dp[s][j] = ans; return ans;}// Function to calculate and// return maximum number of fruitsint maxFruit(vector<int> tree[], int NodesWithFruits[], int n, int m, int k){ // resetting dp table and Fruit array for (int i = 0; i < N; i++) { for (int j = 0; j < 20; j++) dp[i][j] = -1; Fruit[i] = 0; } // This array is used to mark // which nodes contain Fruits for (int i = 0; i < m; i++) Fruit[NodesWithFruits[i]] = 1; dfs1(tree, 1, 0, 0); int ans = dfs2(tree, 1, 0, 0, k); return ans;}// Function to add Edgevoid addEdge(vector<int> tree[], int u, int v){ tree[u].push_back(v); tree[v].push_back(u);}// Driver Codeint main(){ int n = 12; // Number of nodes int k = 2; // Number of allowed jumps vector<int> tree[N]; // Edges addEdge(tree, 1, 2); addEdge(tree, 1, 3); addEdge(tree, 2, 4); addEdge(tree, 2, 5); addEdge(tree, 5, 9); addEdge(tree, 9, 10); addEdge(tree, 9, 11); addEdge(tree, 11, 12); addEdge(tree, 3, 7); addEdge(tree, 7, 6); addEdge(tree, 7, 8); int NodesWithFruits[] = { 2, 4, 5, 7, 8, 9, 11, 12 }; // Number of nodes with fruits int m = sizeof(NodesWithFruits) / sizeof(NodesWithFruits[0]); int ans = maxFruit(tree, NodesWithFruits, n, m, k); cout << ans << endl; return 0;} |
Java
// Program to demonstrate tree traversal with// ability to jump between nodes of same heightimport java.util.*;public class GFG { static int N; static ArrayList<ArrayList<Integer> > H; // Arrays declaration static int[] Fruit; static int[] Parent; static int[][] dp; //[N][20] // Function for DFS static void dfs1(ArrayList<ArrayList<Integer> > tree, int s, int p, int h) { Parent[s] = p; int i; H.get(h).add(s); for (i = 0; i < tree.get(s).size(); i++) { int v = tree.get(s).get(i); if (v != p) dfs1(tree, v, s, h + 1); } } // Function for DFS static int dfs2(ArrayList<ArrayList<Integer> > tree, int s, int p, int h, int j) { int i; int ans = 0; if (dp[s][j] != -1) return dp[s][j]; // jump if (j > 0) { for (i = 0; i < H.get(h).size(); i++) { int v = H.get(h).get(i); if (v != s) ans = Math.max( ans, dfs2(tree, v, Parent[v], h, j - 1)); } } // climb for (i = 0; i < tree.get(s).size(); i++) { int v = tree.get(s).get(i); if (v != p) ans = Math.max(ans, dfs2(tree, v, s, h + 1, j)); } if (Fruit[s] == 1) ans++; dp[s][j] = ans; return ans; } // Function to calculate and // return maximum number of fruits static int maxFruit(ArrayList<ArrayList<Integer> > tree, int NodesWithFruits[], int n, int m, int k) { // resetting dp table and Fruit array for (int i = 0; i < N; i++) { for (int j = 0; j < 20; j++) dp[i][j] = -1; Fruit[i] = 0; } // This array is used to mark // which nodes contain Fruits for (int i = 0; i < m; i++) Fruit[NodesWithFruits[i]] = 1; dfs1(tree, 1, 0, 0); int ans = dfs2(tree, 1, 0, 0, k); return ans; } // Function to add Edge static void addEdge(ArrayList<ArrayList<Integer> > tree, int u, int v) { tree.get(u).add(v); tree.get(v).add(u); } public static void main(String[] args) { N = 1000; H = new ArrayList<>(); Fruit = new int[N]; Parent = new int[N]; dp = new int[N][20]; int n = 12; // Number of nodes int k = 2; // Number of allowed jumps ArrayList<ArrayList<Integer> > tree = new ArrayList<>(); for (int i = 0; i < N; i++) { tree.add(new ArrayList<>()); H.add(new ArrayList<>()); } // Edges addEdge(tree, 1, 2); addEdge(tree, 1, 3); addEdge(tree, 2, 4); addEdge(tree, 2, 5); addEdge(tree, 5, 9); addEdge(tree, 9, 10); addEdge(tree, 9, 11); addEdge(tree, 11, 12); addEdge(tree, 3, 7); addEdge(tree, 7, 6); addEdge(tree, 7, 8); int NodesWithFruits[] = { 2, 4, 5, 7, 8, 9, 11, 12 }; // Number of nodes with fruits int m = NodesWithFruits.length; int ans = maxFruit(tree, NodesWithFruits, n, m, k); System.out.println(ans); }}// This code is contributed by karandeep1234 |
Python3
# Program to demonstrate tree traversal with# ability to jump between nodes of same heightimport sysN = 1000H = [[] for _ in range(N)]# Arrays declarationFruit = [0] * NParent = [0] * Ndp = [[-1] * 20 for _ in range(N)]# Function for DFSdef dfs1(tree, s, p, h): Parent[s] = p for i in range(len(tree[s])): v = tree[s][i] if v != p: dfs1(tree, v, s, h + 1) H[h].append(s)# Function for DFSdef dfs2(tree, s, p, h, j): ans = 0 if dp[s][j] != -1: return dp[s][j] # jump if j > 0: for i in range(len(H[h])): v = H[h][i] if v != s: ans = max(ans, dfs2(tree, v, Parent[v], h, j - 1)) # climb for i in range(len(tree[s])): v = tree[s][i] if v != p: ans = max(ans, dfs2(tree, v, s, h + 1, j)) if Fruit[s] == 1: ans += 1 dp[s][j] = ans return ans# Function to calculate and# return maximum number of fruitsdef maxFruit(tree, NodesWithFruits, n, m, k): # resetting dp table and Fruit array for i in range(N): for j in range(20): dp[i][j] = -1 Fruit[i] = 0 # This array is used to mark # which nodes contain Fruits for i in range(m): Fruit[NodesWithFruits[i]] = 1 dfs1(tree, 1, 0, 0) ans = dfs2(tree, 1, 0, 0, k) return ans# Function to add Edgedef addEdge(tree, u, v): tree[u].append(v) tree[v].append(u)# Driver Codeif __name__ == '__main__': n = 12 # Number of nodes k = 2 # Number of allowed jumps tree = [[] for _ in range(N)] # Edges addEdge(tree, 1, 2) addEdge(tree, 1, 3) addEdge(tree, 2, 4) addEdge(tree, 2, 5) addEdge(tree, 5, 9) addEdge(tree, 9, 10) addEdge(tree, 9, 11) addEdge(tree, 11, 12) addEdge(tree, 3, 7) addEdge(tree, 7, 6) addEdge(tree, 7, 8) NodesWithFruits = [2, 4, 5, 7, 8, 9, 11, 12] # Number of nodes with fruits m = len(NodesWithFruits) ans = maxFruit(tree, NodesWithFruits, n, m, k) print(ans) # This code is contributed by sanjanasikarwar24 |
C#
// Program to demonstrate tree traversal with// ability to jump between nodes of same heightusing System;using System.Collections;using System.Collections.Generic;public class GFG { static int N; static List<List<int> > H; // Arrays declaration static int[] Fruit; static int[] Parent; static int[, ] dp; //[N][20] // Function for DFS static void dfs1(List<List<int> > tree, int s, int p, int h) { Parent[s] = p; int i; H[h].Add(s); for (i = 0; i < tree[s].Count; i++) { int v = tree[s][i]; if (v != p) dfs1(tree, v, s, h + 1); } } // Function for DFS static int dfs2(List<List<int> > tree, int s, int p, int h, int j) { int i; int ans = 0; if (dp[s, j] != -1) return dp[s, j]; // jump if (j > 0) { for (i = 0; i < H[h].Count; i++) { int v = H[h][i]; if (v != s) ans = Math.Max( ans, dfs2(tree, v, Parent[v], h, j - 1)); } } // climb for (i = 0; i < tree[s].Count; i++) { int v = tree[s][i]; if (v != p) ans = Math.Max(ans, dfs2(tree, v, s, h + 1, j)); } if (Fruit[s] == 1) ans++; dp[s, j] = ans; return ans; } // Function to calculate and // return maximum number of fruits static int maxFruit(List<List<int> > tree, int[] NodesWithFruits, int n, int m, int k) { // resetting dp table and Fruit array for (int i = 0; i < N; i++) { for (int j = 0; j < 20; j++) dp[i, j] = -1; Fruit[i] = 0; } // This array is used to mark // which nodes contain Fruits for (int i = 0; i < m; i++) Fruit[NodesWithFruits[i]] = 1; dfs1(tree, 1, 0, 0); int ans = dfs2(tree, 1, 0, 0, k); return ans; } // Function to add Edge static void addEdge(List<List<int> > tree, int u, int v) { tree[u].Add(v); tree[v].Add(u); } public static void Main(string[] args) { N = 1000; H = new List<List<int> >(); Fruit = new int[N]; Parent = new int[N]; dp = new int[N, 20]; int n = 12; // Number of nodes int k = 2; // Number of allowed jumps List<List<int> > tree = new List<List<int> >(); for (int i = 0; i < N; i++) { tree.Add(new List<int>()); H.Add(new List<int>()); } // Edges addEdge(tree, 1, 2); addEdge(tree, 1, 3); addEdge(tree, 2, 4); addEdge(tree, 2, 5); addEdge(tree, 5, 9); addEdge(tree, 9, 10); addEdge(tree, 9, 11); addEdge(tree, 11, 12); addEdge(tree, 3, 7); addEdge(tree, 7, 6); addEdge(tree, 7, 8); int[] NodesWithFruits = { 2, 4, 5, 7, 8, 9, 11, 12 }; // Number of nodes with fruits int m = NodesWithFruits.Length; int ans = maxFruit(tree, NodesWithFruits, n, m, k); Console.WriteLine(ans); }}// This code is contributed by Karandeep1234 |
Javascript
// Javascript code for the above approachconst N = 1000;let H = new Array(N);for (let i = 0; i < N; i++) { H[i] = [];}// Arrays declarationlet Fruit = new Array(N).fill(0);let Parent = new Array(N).fill(0);let dp = new Array(N);for (let i = 0; i < N; i++) { dp[i] = new Array(20).fill(-1);}// Function for DFSfunction dfs1(tree, s, p, h) { Parent[s] = p; for (let i = 0; i < tree[s].length; i++) { let v = tree[s][i]; if (v !== p) { dfs1(tree, v, s, h + 1); } } H[h].push(s);}// Function for DFSfunction dfs2(tree, s, p, h, j) { let ans = 0; if (dp[s][j] !== -1) { return dp[s][j]; } // jump if (j > 0) { for (let i = 0; i < H[h].length; i++) { let v = H[h][i]; if (v !== s) { ans = Math.max(ans, dfs2(tree, v, Parent[v], h, j - 1)); } } } // climb for (let i = 0; i < tree[s].length; i++) { let v = tree[s][i]; if (v !== p) { ans = Math.max(ans, dfs2(tree, v, s, h + 1, j)); } } if (Fruit[s] === 1) { ans += 1; } dp[s][j] = ans; return ans;}// Function to calculate and// return maximum number of fruitsfunction maxFruit(tree, NodesWithFruits, n, m, k) { // resetting dp table and Fruit array for (let i = 0; i < N; i++) { for (let j = 0; j < 20; j++) { dp[i][j] = -1; } Fruit[i] = 0; } // This array is used to mark // which nodes contain Fruits for (let i = 0; i < m; i++) { Fruit[NodesWithFruits[i]] = 1; } dfs1(tree, 1, 0, 0); let ans = dfs2(tree, 1, 0, 0, k); return ans;}// Function to add Edgefunction addEdge(tree, u, v) { tree[u].push(v); tree[v].push(u);}// Driver Code let n = 12; // Number of nodes let k = 2; // Number of allowed jumpslet tree = new Array(N);for (let i = 0; i < N; i++) {tree[i] = [];}// EdgesaddEdge(tree, 1, 2);addEdge(tree, 1, 3);addEdge(tree, 2, 4);addEdge(tree, 2, 5);addEdge(tree, 5, 9);addEdge(tree, 9, 10);addEdge(tree, 9, 11);addEdge(tree, 11, 12);addEdge(tree, 3, 7);addEdge(tree, 7, 6);addEdge(tree, 7, 8);let NodesWithFruits = [2, 4, 5, 7, 8, 9, 11, 12];// Number of nodes with fruitslet m = NodesWithFruits.length;let ans = maxFruit(tree, NodesWithFruits, n, m, k);console.log(ans);// This code is contributed by lokeshpotta20. |
Output
7
Complexity Analysis:
- Time Complexity: O(n*n*k) (worst case, eg: 2 level tree with the root having n-1 child nodes)
- 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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
