Given a Binary tree, the task is to print all possible root-to-leaf paths having a maximum number of even valued nodes.
Examples:
Input:
2 / \ 6 3 / \ \ 4 7 11 / \ \ 10 12 1Output:
2 -> 6 -> 4 -> 10
2 -> 6 -> 4 -> 12
Explanation:
Count of even nodes on the path 2 -> 6 -> 4 -> 10 = 4
Count of even nodes on the path 2 -> 6 -> 4 -> 12 = 4
Count of even nodes on the path 2 -> 6 -> 7 -> 1 = 2
Count of even nodes on the path 2 -> 3 -> 11 = 1
Therefore, the paths consisting of maximum count of even nodes are {2 -> 6 -> 4 -> 10} and {2 -> 6 -> 4 -> 12 }.Input:
5 / \ 6 3 / \ \ 4 9 2Output: 5 -> 6 -> 4.
Approach: The problem can be solved using Preorder Traversal. The idea is to traverse the given Binary Tree and find the maximum count of even nodes possible in a root-to-leaf path. Finally, traverse the tree and print all possible root-to-leaf paths having the maximum count of even nodes. Follow the steps below to solve the problem:
- Initialize two variables, say cntMaxEven and cntEven to store the maximum count of even nodes from the root to a leaf node and count of even nodes from root to a leaf node.
- Traverse the tree and check the following conditions:
- Check if current node is a leaf node and cntEven > cntMaxEven or not. If found to be true then update cntMaxEven = cntEven.
- Otherwise, check if the current node is an even node or not. If found to be true, then Update cntEven += 1.
- Finally, traverse the tree and print all possible root-to-leaf paths having a count of even nodes equal to cntMaxEven.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of the binary treestruct Node { // Stores data int data; // Stores left child Node* left; // Stores right child Node* right; // Initialize a node // of binary tree Node(int val) { // Update data; data = val; left = right = NULL; }};// Function to find maximum count// of even nodes in a pathint cntMaxEvenNodes(Node* root){ // If the tree is an // empty binary tree. if (root == NULL) { return 0; } // Stores count of even nodes // in current subtree int cntEven = 0; // If root node is // an even node if (root->data % 2 == 0) { // Update cntEven cntEven += 1; } // Stores count of even nodes // in left subtree. int X = cntMaxEvenNodes( root->left); // Stores count of even nodes // in right subtree. int Y = cntMaxEvenNodes( root->right); // cntEven cntEven += max(X, Y); return cntEven;}// Function to print paths having// count of even nodes equal// to maximum count of even nodesvoid printPath(Node* root, int cntEven, int cntMaxEven, vector<int>& path){ // If the tree is an // empty Binary Tree if (root == NULL) { return; } // If current node value is even if (root->data % 2 == 0) { path.push_back( root->data); cntEven += 1; } // If current node is // a leaf node if (root->left == NULL && root->right == NULL) { // If count of even nodes in // path is equal to cntMaxEven if (cntEven == cntMaxEven) { // Stores length of path int N = path.size(); // Print path for (int i = 0; i < N - 1; i++) { cout << path[i] << " -> "; } cout << path[N - 1] << endl; } } // Left subtree printPath(root->left, cntEven, cntMaxEven, path); // Right subtree printPath(root->right, cntEven, cntMaxEven, path); // If current node is even if (root->data % 2 == 0) { path.pop_back(); // Update cntEven cntEven--; }}// Utility Function to print path// from root to leaf node having// maximum count of even nodesvoid printMaxPath(Node* root){ // Stores maximum count of even // nodes of a path in the tree int cntMaxEven; cntMaxEven = cntMaxEvenNodes(root); // Stores path of tree having // even nodes vector<int> path; printPath(root, 0, cntMaxEven, path);}// Driver codeint main(){ // Create tree. Node* root = NULL; root = new Node(2); root->left = new Node(6); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(7); root->right->right = new Node(11); root->left->left->left = new Node(10); root->left->left->right = new Node(12); root->left->right->right = new Node(1); printMaxPath(root);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Structure of the binary treestatic class Node { // Stores data int data; // Stores left child Node left; // Stores right child Node right; // Initialize a node // of binary tree Node(int val) { // Update data; data = val; left = right = null; }};// Function to find maximum count// of even nodes in a pathstatic int cntMaxEvenNodes(Node root){ // If the tree is an // empty binary tree. if (root == null) { return 0; } // Stores count of even nodes // in current subtree int cntEven = 0; // If root node is // an even node if (root.data % 2 == 0) { // Update cntEven cntEven += 1; } // Stores count of even nodes // in left subtree. int X = cntMaxEvenNodes(root.left); // Stores count of even nodes // in right subtree. int Y = cntMaxEvenNodes(root.right); // cntEven cntEven += Math.max(X, Y); return cntEven;}// Function to print paths having// count of even nodes equal// to maximum count of even nodesstatic void printPath(Node root, int cntEven, int cntMaxEven, Vector<Integer> path){ // If the tree is an // empty Binary Tree if (root == null) { return; } // If current node value is even if (root.data % 2 == 0) { path.add(root.data); cntEven += 1; } // If current node is // a leaf node if (root.left == null && root.right == null) { // If count of even nodes in // path is equal to cntMaxEven if (cntEven == cntMaxEven) { // Stores length of path int N = path.size(); // Print path for(int i = 0; i < N - 1; i++) { System.out.print(path.get(i) + " -> "); } System.out.print(path.get(N - 1) + "\n"); } } // Left subtree printPath(root.left, cntEven, cntMaxEven, path); // Right subtree printPath(root.right, cntEven, cntMaxEven, path); // If current node is even if (root.data % 2 == 0) { path.remove(path.size() - 1); // Update cntEven cntEven--; }}// Utility Function to print path// from root to leaf node having// maximum count of even nodesstatic void printMaxPath(Node root){ // Stores maximum count of even // nodes of a path in the tree int cntMaxEven; cntMaxEven = cntMaxEvenNodes(root); // Stores path of tree having // even nodes Vector<Integer> path = new Vector<>(); printPath(root, 0, cntMaxEven, path);}// Driver codepublic static void main(String[] args){ // Create tree. Node root = null; root = new Node(2); root.left = new Node(6); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(7); root.right.right = new Node(11); root.left.left.left = new Node(10); root.left.left.right = new Node(12); root.left.right.right = new Node(1); printMaxPath(root);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approach# Structure of the binary treeclass newNode: def __init__(self, val): self.data = val self.left = None self.right = Nonepath = []# Function to find maximum count# of even nodes in a pathdef cntMaxEvenNodes(root): # If the tree is an # empty binary tree. if (root == None): return 0 # Stores count of even nodes # in current subtree cntEven = 0 # If root node is # an even node if (root.data % 2 == 0): # Update cntEven cntEven += 1 # Stores count of even nodes # in left subtree. X = cntMaxEvenNodes(root.left) # Stores count of even nodes # in right subtree. Y = cntMaxEvenNodes(root.right) # cntEven cntEven += max(X, Y) return cntEven# Function to print paths having# count of even nodes equal# to maximum count of even nodesdef printPath(root, cntEven, cntMaxEven): global path # If the tree is an # empty Binary Tree if (root == None): return # If current node value is even if (root.data % 2 == 0): path.append(root.data) cntEven += 1 # If current node is # a leaf node if (root.left == None and root.right == None): # If count of even nodes in # path is equal to cntMaxEven if (cntEven == cntMaxEven): # Stores length of path N = len(path) # Print path for i in range(N - 1): print(path[i], end = "->") print(path[N - 1]) # Left subtree printPath(root.left, cntEven, cntMaxEven) # Right subtree printPath(root.right, cntEven, cntMaxEven) # If current node is even if (root.data % 2 == 0): path.remove(path[len(path) - 1]) # Update cntEven cntEven -= 1# Utility Function to print path# from root to leaf node having# maximum count of even nodesdef printMaxPath(root): global path # Stores maximum count of even # nodes of a path in the tree cntMaxEven = cntMaxEvenNodes(root) printPath(root, 0, cntMaxEven)# Driver codeif __name__ == '__main__': # Create tree. root = None root = newNode(2) root.left = newNode(6) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(7) root.right.right = newNode(11) root.left.left.left = newNode(10) root.left.left.right = newNode(12) root.left.right.right = newNode(1) printMaxPath(root)# This code is contributed by bgangwar59 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ // Structure of the binary treeclass Node { // Stores data public int data; // Stores left child public Node left; // Stores right child public Node right; // Initialize a node // of binary tree public Node(int val) { // Update data; data = val; left = right = null; }};// Function to find maximum count// of even nodes in a pathstatic int cntMaxEvenNodes(Node root){ // If the tree is an // empty binary tree. if (root == null) { return 0; } // Stores count of even // nodes in current subtree int cntEven = 0; // If root node is // an even node if (root.data % 2 == 0) { // Update cntEven cntEven += 1; } // Stores count of even // nodes in left subtree. int X = cntMaxEvenNodes(root.left); // Stores count of even nodes // in right subtree. int Y = cntMaxEvenNodes(root.right); // cntEven cntEven += Math.Max(X, Y); return cntEven;}// Function to print paths having// count of even nodes equal// to maximum count of even nodesstatic void printPath(Node root, int cntEven, int cntMaxEven, List<int> path){ // If the tree is an // empty Binary Tree if (root == null) { return; } // If current node value // is even if (root.data % 2 == 0) { path.Add(root.data); cntEven += 1; } // If current node is // a leaf node if (root.left == null && root.right == null) { // If count of even nodes in // path is equal to cntMaxEven if (cntEven == cntMaxEven) { // Stores length of path int N = path.Count; // Print path for(int i = 0; i < N - 1; i++) { Console.Write(path[i] + " -> "); } Console.Write(path[N - 1] + "\n"); } } // Left subtree printPath(root.left, cntEven, cntMaxEven, path); // Right subtree printPath(root.right, cntEven, cntMaxEven, path); // If current node is even if (root.data % 2 == 0) { path.RemoveAt(path.Count - 1); // Update cntEven cntEven--; }}// Utility Function to print path// from root to leaf node having// maximum count of even nodesstatic void printMaxPath(Node root){ // Stores maximum count of even // nodes of a path in the tree int cntMaxEven; cntMaxEven = cntMaxEvenNodes(root); // Stores path of tree having // even nodes List<int> path = new List<int>(); printPath(root, 0, cntMaxEven, path);}// Driver codepublic static void Main(String[] args){ // Create tree. Node root = null; root = new Node(2); root.left = new Node(6); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(7); root.right.right = new Node(11); root.left.left.left = new Node(10); root.left.left.right = new Node(12); root.left.right.right = new Node(1); printMaxPath(root);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to implement// the above approach// Structure of the binary treeclass Node{ constructor(val) { this.left = null; this.right = null; this.data = val; }}// Function to find maximum count// of even nodes in a pathfunction cntMaxEvenNodes(root){ // If the tree is an // empty binary tree. if (root == null) { return 0; } // Stores count of even nodes // in current subtree let cntEven = 0; // If root node is // an even node if (root.data % 2 == 0) { // Update cntEven cntEven += 1; } // Stores count of even nodes // in left subtree. let X = cntMaxEvenNodes(root.left); // Stores count of even nodes // in right subtree. let Y = cntMaxEvenNodes(root.right); // cntEven cntEven += Math.max(X, Y); return cntEven;}// Function to print paths having// count of even nodes equal// to maximum count of even nodesfunction printPath(root, cntEven, cntMaxEven, path){ // If the tree is an // empty Binary Tree if (root == null) { return; } // If current node value is even if (root.data % 2 == 0) { path.push(root.data); cntEven += 1; } // If current node is // a leaf node if (root.left == null && root.right == null) { // If count of even nodes in // path is equal to cntMaxEven if (cntEven == cntMaxEven) { // Stores length of path let N = path.length; // Print path for(let i = 0; i < N - 1; i++) { document.write(path[i] + " -> "); } document.write(path[N - 1] + "</br>"); } } // Left subtree printPath(root.left, cntEven, cntMaxEven, path); // Right subtree printPath(root.right, cntEven, cntMaxEven, path); // If current node is even if (root.data % 2 == 0) { path.pop(); // Update cntEven cntEven--; }}// Utility Function to print path// from root to leaf node having// maximum count of even nodesfunction printMaxPath(root){ // Stores maximum count of even // nodes of a path in the tree let cntMaxEven; cntMaxEven = cntMaxEvenNodes(root); // Stores path of tree having // even nodes let path = []; printPath(root, 0, cntMaxEven, path);}// Driver code// Create tree.let root = null;root = new Node(2);root.left = new Node(6);root.right = new Node(3);root.left.left = new Node(4);root.left.right = new Node(7);root.right.right = new Node(11);root.left.left.left = new Node(10);root.left.left.right = new Node(12);root.left.right.right = new Node(1);printMaxPath(root);// This code is contributed by suresh07</script> |
Output:
2 -> 6 -> 4 -> 10 2 -> 6 -> 4 -> 12
Time Complexity: O(N), where N is the number of nodes in the binary tree.
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!
