Intuition and Approach
To print the paths that contain the maximum number of even nodes, we first have to find the maximum number of even nodes in all possible paths.
- We will create a variable ‘COUNT’ (to store the maximum number of even nodes in all possible paths) and another variable ‘TEMP’ (to store the count of even nodes along a path).
-
Now using pre-order traversal, we can find the value of ‘COUNT’. If the current node is an even node then we will increase the value of ‘TEMP’ by 1. Now rest of the work can be done by recursion. We will use Recursion to bring the value of the maximum number of even nodes that are present in the left and right subtree, and finally, We can update the value of ‘FINAL_COUNT’ from the will be maximum among two values (from left and right subtree).
Then after finding the ‘FINAL_COUNT’, we can simply print those paths only which have a count of even nodes equal to ‘FINAL_COUNT’.
Things will become more clear by the code.
Code
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
// Structure of a tree node.
class BinaryTreeNode
{
public:
int data;
BinaryTreeNode * left;
BinaryTreeNode * right;
// Constructor.
BinaryTreeNode(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Function to find the count of Maximum even nodes in a Binary Tree.
int maxEvenNode(BinaryTreeNode *root)
{
// If the root is NULL, the answer would be 0.
if (root == NULL)
{
return 0;
}
// This will store the number of even nodes in a subtree.
int temp = 0;
// If the root is even then the count of 'TEMP' will be increased.
if (root->data % 2 == 0)
{
temp += 1;
}
// Calling recursion on the left and right subtree.
int X = maxEvenNode(root->left);
int Y = maxEvenNode(root->right);
temp = temp + max(X, Y);
return temp;
}
// Function to print those paths whose count of even nodes is 'COUNT'.
void printPath(BinaryTreeNode *root, int temp, int count, vector<int> &path)
{
if (root == NULL)
{
return;
}
// If it's even. Then we will increase the value of temp by 1 and push it in our 'PATH' vector.
if (root->data % 2 == 0)
{
path.push_back(root->data);
temp += 1;
}
if (root->left == NULL && root->right == NULL)
{
// If it’s maximum count, then we will print the path.
if (count == temp)
{
for (int i = 0; i < path.size() - 1; i++)
cout << path[i] << " -> ";
cout << path[path.size() - 1] << endl;
}
}
// Calling function on left and right subtree.
printPath(root->left, temp, count, path);
printPath(root->right, temp, count, path);
// Removing nodes if they are even (backtrack).
if (root->data % 2 == 0)
{
path.pop_back();
temp--;
}
}
// Function to print paths with the maximum number of even nodes.
void printMaxPath(BinaryTreeNode *root)
{
// 'COUNT' stores the maximum number of even nodes in the tree.
int count = maxEvenNode(root);
vector<int> path;
// Printing paths with the count of even nodes as 'COUNT'.
printPath(root, 0, count, path);
}
// Main function.
int main()
{
// Input Tree.
BinaryTreeNode *root = NULL;
root = new BinaryTreeNode(10);
root->left = new BinaryTreeNode(8);
root->right = new BinaryTreeNode(24);
root->left->left = new BinaryTreeNode(4);
root->left->right = new BinaryTreeNode(6);
root->right->right = new BinaryTreeNode(6);
root->left->left->left = new BinaryTreeNode(12);
root->right->left = new BinaryTreeNode(11);
root->right->right->right = new BinaryTreeNode(10);
// Calling 'printMaxPath()' function.
printMaxPath(root);
}
You can also try this code with Online C++ Compiler
Input
Output
10 -> 8 -> 4 -> 12
10 -> 24 -> 6 -> 10
Time Complexity
O(N), where ‘N’ is the number of nodes in the tree.
As we are traversing every node in the tree only twice (we are performing pre-order traversal). Thus, the time complexity is O(N) + O(N) ~ O(N).
Space Complexity
O(N), where ‘N’ is the number of nodes in the tree.
This is the space used by the recursion stack. It will be equal to the height of the tree. In the worst case, the height would be ‘N’ (skew Tree) thus the space complexity will be O(N).
Must Read Recursion in Data Structure
Frequently Asked Questions
What is a Binary Tree?
A Binary Tree is a type of Tree Data Structure where any node in the tree can have a maximum of two children.
What is a Leaf Node?
The Node in the Binary tree for which both its children that is the left and right child are null is called a leaf node
Conclusion
We saw how we could solve the problem, ‘print all root-to-leaf paths with a maximum count of even nodes’ using pre-order traversal. You must be thinking that this was an easy one, and now I have mastered binary trees. But a ninja should never be overconfident, and he should always keep a check on his problem-solving skills.
Recommended Problems:
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
8+ registered 