Given a binary tree and an integer K, the task is to print the paths from root to leaf with the maximum element greater than or equal to K. Print -1 if there exists no such path.
Examples:
Input: K = 25,
10
/ \
5 8
/ \ / \
29 2 1 98
/ \
20 50
Output: (10, 5, 29, 20), (10, 8, 98, 50)
Explanation:
The maximum value in the path 10
-> 5 -> 29 -> 20
is 29 which is greater than 25.
The maximum value in the path 10
-> 8 -> 98 -> 50
is 98 which is greater than 25.
Input: K = 5
2
/ \
1 4
/
0
Output: -1
Explanation:
None of the paths from the root to a leaf
has the value greater than 5.
Approach: The idea is to check if a node contains a value greater than or equal to ‘K’. If yes, then all the subtrees of that node is a valid path. The following steps can be followed to compute the answer:
- For every node, check if the current node value is greater than ‘K’ or not.
- If yes, then insert it into a vector and set a flag variable to 1. This signifies that all the paths going through this node will be printed.
- Repeat the above steps using recursion. The function is recursively called for the left and right subtrees.
- Finally, by using the concept of backtracking, print the path from the vector.
Below is the implementation of the above approach:
CPP
// C++ program to print paths with maximum// element in the path greater than K#include <bits/stdc++.h>using namespace std;// A Binary Tree nodestruct Node { int data; struct Node *left, *right;};// A utility function to create a new nodestruct Node* newNode(int data){ struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return (newNode);}// A recursive function to print the paths// whose maximum element is greater than// or equal to K.void findPathUtil(Node* root, int k, vector<int> path, int flag, int& ans){ if (root == NULL) return; // If the current node value is greater than // or equal to k, then all the subtrees // following that node will get printed, // flag = 1 indicates to print the required path if (root->data >= k) flag = 1; // If the leaf node is encountered, then the path is // printed if the size of the path vector is // greater than 0 if (root->left == NULL && root->right == NULL) { if (flag == 1) { ans = 1; cout << "("; for (int i = 0; i < path.size(); i++) { cout << path[i] << ", "; } cout << root->data << "), "; } return; } // Append the node to the path vector path.push_back(root->data); // Recur left and right subtrees findPathUtil(root->left, k, path, flag, ans); findPathUtil(root->right, k, path, flag, ans); // Backtracking to return the vector // and print the path if the flag is 1 path.pop_back();}// Function to initialize the variables// and call the utility function to print// the paths with maximum values greater than// or equal to Kvoid findPath(Node* root, int k){ // Initialize flag int flag = 0; // ans is used to check empty condition int ans = 0; vector<int> v; // Call function that print path findPathUtil(root, k, v, flag, ans); // If the path doesn't exist if (ans == 0) cout << "-1";}// Driver codeint main(void){ int K = 25; /* Constructing the following tree: 10 / \ 5 8 / \ / \ 29 2 1 98 / \ 20 50 */ struct Node* root = newNode(10); root->left = newNode(5); root->right = newNode(8); root->left->left = newNode(29); root->left->right = newNode(2); root->right->right = newNode(98); root->right->left = newNode(1); root->right->right->right = newNode(50); root->left->left->left = newNode(20); findPath(root, K); return 0;} |
Java
// Java program to print paths with maximum// element in the path greater than Kimport java.util.*;class GFG{// A Binary Tree nodestatic class Node { int data; Node left, right;};static int ans;// A utility function to create a new nodestatic Node newNode(int data){ Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode);}// A recursive function to print the paths// whose maximum element is greater than// or equal to K.static void findPathUtil(Node root, int k, Vector<Integer> path, int flag){ if (root == null) return; // If the current node value is greater than // or equal to k, then all the subtrees // following that node will get printed, // flag = 1 indicates to print the required path if (root.data >= k) flag = 1; // If the leaf node is encountered, then the path is // printed if the size of the path vector is // greater than 0 if (root.left == null && root.right == null) { if (flag == 1) { ans = 1; System.out.print("("); for (int i = 0; i < path.size(); i++) { System.out.print(path.get(i)+ ", "); } System.out.print(root.data+ "), "); } return; } // Append the node to the path vector path.add(root.data); // Recur left and right subtrees findPathUtil(root.left, k, path, flag); findPathUtil(root.right, k, path, flag); // Backtracking to return the vector // and print the path if the flag is 1 path.remove(path.size()-1);}// Function to initialize the variables// and call the utility function to print// the paths with maximum values greater than// or equal to Kstatic void findPath(Node root, int k){ // Initialize flag int flag = 0; // ans is used to check empty condition ans = 0; Vector<Integer> v = new Vector<Integer>(); // Call function that print path findPathUtil(root, k, v, flag); // If the path doesn't exist if (ans == 0) System.out.print("-1");}// Driver codepublic static void main(String [] args){ int K = 25; /* Constructing the following tree: 10 / \ 5 8 / \ / \ 29 2 1 98 / \ 20 50*/ Node root = newNode(10); root.left = newNode(5); root.right = newNode(8); root.left.left = newNode(29); root.left.right = newNode(2); root.right.right = newNode(98); root.right.left = newNode(1); root.right.right.right = newNode(50); root.left.left.left = newNode(20); findPath(root, K);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to construct string from binary tree# A Binary Tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# A recursive function to print the paths# whose maximum element is greater than# or equal to K.def findPathUtil(root: Node, k: int, path: list, flag: int): global ans if root is None: return # If the current node value is greater than # or equal to k, then all the subtrees # following that node will get printed, # flag = 1 indicates to print the required path if root.data >= k: flag = 1 # If the leaf node is encountered, then the path is # printed if the size of the path vector is # greater than 0 if root.left is None and root.right is None: if flag: ans = 1 print("(", end = "") for i in range(len(path)): print(path[i], end = ", ") print(root.data, end = "), ") return # Append the node to the path vector path.append(root.data) # Recur left and right subtrees findPathUtil(root.left, k, path, flag) findPathUtil(root.right, k, path, flag) # Backtracking to return the vector # and print the path if the flag is 1 path.pop()# Function to initialize the variables# and call the utility function to print# the paths with maximum values greater than# or equal to Kdef findPath(root: Node, k: int): global ans # Initialize flag flag = 0 # ans is used to check empty condition ans = 0 v = [] # Call function that print path findPathUtil(root, k, v, flag) # If the path doesn't exist if ans == 0: print(-1)# Driver Codeif __name__ == "__main__": ans = 0 k = 25 # Constructing the following tree: # 10 # / \ # 5 8 # / \ / \ # 29 2 1 98 # / \ # 20 50 root = Node(10) root.left = Node(5) root.right = Node(8) root.left.left = Node(29) root.left.right = Node(2) root.right.right = Node(98) root.right.left = Node(1) root.right.right.right = Node(50) root.left.left.left = Node(20) findPath(root, k)# This code is contributed by# sanjeev2552 |
C#
// C# program to print paths with maximum// element in the path greater than Kusing System;using System.Collections.Generic;class GFG{// A Binary Tree nodeclass Node { public int data; public Node left, right;};static int ans;// A utility function to create a new nodestatic Node newNode(int data){ Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode);}// A recursive function to print the paths// whose maximum element is greater than// or equal to K.static void findPathUtil(Node root, int k, List<int> path, int flag){ if (root == null) return; // If the current node value is greater than // or equal to k, then all the subtrees // following that node will get printed, // flag = 1 indicates to print the required path if (root.data >= k) flag = 1; // If the leaf node is encountered, then the path is // printed if the size of the path vector is // greater than 0 if (root.left == null && root.right == null) { if (flag == 1) { ans = 1; Console.Write("("); for (int i = 0; i < path.Count; i++) { Console.Write(path[i] + ", "); } Console.Write(root.data + "), "); } return; } // Append the node to the path vector path.Add(root.data); // Recur left and right subtrees findPathUtil(root.left, k, path, flag); findPathUtil(root.right, k, path, flag); // Backtracking to return the vector // and print the path if the flag is 1 path.RemoveAt(path.Count-1);}// Function to initialize the variables// and call the utility function to print// the paths with maximum values greater than// or equal to Kstatic void findPath(Node root, int k){ // Initialize flag int flag = 0; // ans is used to check empty condition ans = 0; List<int> v = new List<int>(); // Call function that print path findPathUtil(root, k, v, flag); // If the path doesn't exist if (ans == 0) Console.Write("-1");}// Driver codepublic static void Main(String [] args){ int K = 25; /* Constructing the following tree: 10 / \ 5 8 / \ / \ 29 2 1 98 / \ 20 50*/ Node root = newNode(10); root.left = newNode(5); root.right = newNode(8); root.left.left = newNode(29); root.left.right = newNode(2); root.right.right = newNode(98); root.right.left = newNode(1); root.right.right.right = newNode(50); root.left.left.left = newNode(20); findPath(root, K);}}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to print paths with maximum// element in the path greater than K// A Binary Tree nodeclass Node { constructor() { this.data = 0; this.left = null; this.right = null; }};var ans = 0;// A utility function to create a new nodefunction newNode(data){ var newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode);}// A recursive function to print the paths// whose maximum element is greater than// or equal to K.function findPathUtil(root, k, path, flag){ if (root == null) return; // If the current node value is greater than // or equal to k, then all the subtrees // following that node will get printed, // flag = 1 indicates to print the required path if (root.data >= k) flag = 1; // If the leaf node is encountered, then the path is // printed if the size of the path vector is // greater than 0 if (root.left == null && root.right == null) { if (flag == 1) { ans = 1; document.write("("); for (var i = 0; i < path.length; i++) { document.write(path[i] + ", "); } document.write(root.data + "), "); } return; } // Append the node to the path vector path.push(root.data); // Recur left and right subtrees findPathUtil(root.left, k, path, flag); findPathUtil(root.right, k, path, flag); // Backtracking to return the vector // and print the path if the flag is 1 path.pop();}// Function to initialize the variables// and call the utility function to print// the paths with maximum values greater than// or equal to Kfunction findPath(root, k){ // Initialize flag var flag = 0; // ans is used to check empty condition ans = 0; var v = []; // Call function that print path findPathUtil(root, k, v, flag); // If the path doesn't exist if (ans == 0) document.write("-1");}// Driver codevar K = 25;/* Constructing the following tree: 10 / \ 5 8 / \ / \ 29 2 1 98 / \ 20 50 */var root = newNode(10);root.left = newNode(5);root.right = newNode(8);root.left.left = newNode(29);root.left.right = newNode(2);root.right.right = newNode(98);root.right.left = newNode(1);root.right.right.right = newNode(50);root.left.left.left = newNode(20);findPath(root, K);</script> |
Output:
(10, 5, 29, 20), (10, 8, 98, 50),
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!
