Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition and Approach
3.1.
Code
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
What is a Leaf Node?
5.
Conclusion
Last Updated: Mar 27, 2024

Print all Root-to-Leaf Paths with Maximum Count of Even Nodes

Author Saksham Gupta
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Binary trees are like salt to an interview,i.e., every tech interview is incomplete without binary trees. Thus to get an edge over our competition, it is very important to master binary trees. But when Ninja is here, you don’t have to go to any other place. Today we will be seeing one such important problem on Binary Trees, i.e., Print all root-to-leaf paths with a maximum count of even nodes in a Binary Tree.

Also see, Data Structures

Understanding the Problem

The problem title is self-explanatory. We are given a binary tree, and we have to print all paths from the root to the leaf, which has a maximum count of nodes with an even value.

You will get a better understanding of the problem statement from the following example.

In the following example, we can see that we have two paths (10 - >8 - > 4 - > 12) and (10 - > 24 - > 6 - > 10) with maximum number of nodes with even values i.e., 4.

Thus we will print these two paths.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
}

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.

Previous article
Find if there is a pair in root to a leaf path with a sum equal to the root's data
Next article
Print all root leaf paths with their relative positions
Live masterclass