Given a binary tree of 0s and 1s, the task is to find the maximum number of 1s in any path in the tree. The path may start and end at any node in the tree.
Example:
Input:
1
/ \
0 1
/ \
1 1
/ \
1 0
Output: 4
Approach:
- A function countUntil has been created which returns the maximum count of 1 in any vertical path below that node.
- This path must be a single path and this path must include at-most one child of the node as well as its itself. i.e countUntil returns the max count of 1 in either left child or right child and also includes itself in count if its value is 1.
- So, from any node countUntil(node->left) + countUntil(node->right) + node->value will give the number of 1s in the path which contains the node and its left and right path and no ancestor of the node is considered.
- Taking the maximum of all nodes will give the required answer.
Below is the implementation of the above approach
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// A binary tree nodestruct Node { int data; struct Node *left, *right;};// A utility function to allocate a new nodestruct Node* newNode(int data){ struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return (newNode);}// This function updates overall count of 1 in 'res'// And returns count 1s going through root.int countUntil(Node* root, int& res){ // Base Case if (root == NULL) return 0; // l and r store count of 1s going through left and // right child of root respectively int l = countUntil(root->left, res); int r = countUntil(root->right, res); // maxCount represents the count of 1s when the Node under // consideration is the root of the maxCount path and no // ancestors of the root are there in maxCount path int maxCount; // if the value at node is 1 then its // count will be considered // including the leftCount and the rightCount if (root->data == 1) maxCount = l + r + 1; else maxCount = l + r; // Store the Maximum Result. res = max(res, maxCount); // return max count in a single path. // This path must include at-most one child // of the root as well as itself // if the value at node is 1 // then its count will be considered // including the maximum of leftCount or the rightCount if (root->data == 1) return max(l, r) + 1; else return max(l, r);}// Returns maximum count of 1 in any path// in tree with given rootint findMaxCount(Node* root){ // Initialize result int res = INT_MIN; // Compute and return result countUntil(root, res); return res;}// Driver programint main(void){ struct Node* root = newNode(1); root->left = newNode(0); root->right = newNode(1); root->left->left = newNode(1); root->left->right = newNode(1); root->left->right->left = newNode(1); root->left->right->right = newNode(0); cout << findMaxCount(root); return 0;} |
Java
// Java implementation of the above approachclass GFG{ // A binary tree node static class Node { int data; Node left, right; }; static int res; // A utility function to allocate a new node static Node newNode(int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode); } // This function updates overall count of 1 in 'res' // And returns count 1s going through root. static int countUntil(Node root) { // Base Case if (root == null) return 0; // l and r store count of 1s going through left and // right child of root respectively int l = countUntil(root.left); int r = countUntil(root.right); // maxCount represents the count of 1s when the Node under // consideration is the root of the maxCount path and no // ancestors of the root are there in maxCount path int maxCount; // if the value at node is 1 then its // count will be considered // including the leftCount and the rightCount if (root.data == 1) maxCount = l + r + 1; else maxCount = l + r; // Store the Maximum Result. res = Math.max(res, maxCount); // return max count in a single path. // This path must include at-most one child // of the root as well as itself // if the value at node is 1 // then its count will be considered // including the maximum of leftCount or the rightCount if (root.data == 1) return Math.max(l, r) + 1; else return Math.max(l, r); } // Returns maximum count of 1 in any path // in tree with given root static int findMaxCount(Node root) { // Initialize result res = Integer.MIN_VALUE; // Compute and return result countUntil(root); return res; } // Driver program public static void main(String[] args) { Node root = newNode(1); root.left = newNode(0); root.right = newNode(1); root.left.left = newNode(1); root.left.right = newNode(1); root.left.right.left = newNode(1); root.left.right.right = newNode(0); System.out.print(findMaxCount(root)); }}// This code is contributed by 29AjayKumar |
Python3
# Python implementation of the above approach# A binary tree nodeclass Node: def __init__(self): self.data = 0 self.left = None self.right = None# A utility function to allocate a new nodedef newNode(data): newNode = Node() newNode.data = data newNode.left = newNode.right = None return (newNode)res = 0# This function updates overall count of 1 in 'res'# And returns count 1s going through root.def countUntil( root): global res # Base Case if (root == None): return 0 # l and r store count of 1s going through left and # right child of root respectively l = countUntil(root.left) r = countUntil(root.right) # maxCount represents the count of 1s when the Node under # consideration is the root of the maxCount path and no # ancestors of the root are there in maxCount path maxCount = 0 # if the value at node is 1 then its # count will be considered # including the leftCount and the rightCount if (root.data == 1): maxCount = l + r + 1 else: maxCount = l + r # Store the Maximum Result. res = max(res, maxCount) # return max count in a single path. # This path must include at-most one child # of the root as well as itself # if the value at node is 1 # then its count will be considered # including the maximum of leftCount or the rightCount if (root.data == 1): return max(l, r) + 1 else: return max(l, r)# Returns maximum count of 1 in any path# in tree with given rootdef findMaxCount(root): global res # Initialize result res = -999999 # Compute and return result countUntil(root) return res# Driver programroot = newNode(1)root.left = newNode(0)root.right = newNode(1)root.left.left = newNode(1)root.left.right = newNode(1)root.left.right.left = newNode(1)root.left.right.right = newNode(0)print(findMaxCount(root))# This code is contributed by Arnab Kundu |
C#
// C# implementation of the above approachusing System;class GFG{ // A binary tree node class Node { public int data; public Node left, right; }; static int res; // A utility function to allocate a new node static Node newNode(int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode); } // This function updates overall count of 1 in 'res' // And returns count 1s going through root. static int countUntil(Node root) { // Base Case if (root == null) return 0; // l and r store count of 1s going through left and // right child of root respectively int l = countUntil(root.left); int r = countUntil(root.right); // maxCount represents the count of 1s when the Node under // consideration is the root of the maxCount path and no // ancestors of the root are there in maxCount path int maxCount; // if the value at node is 1 then its // count will be considered // including the leftCount and the rightCount if (root.data == 1) maxCount = l + r + 1; else maxCount = l + r; // Store the Maximum Result. res = Math.Max(res, maxCount); // return max count in a single path. // This path must include at-most one child // of the root as well as itself // if the value at node is 1 // then its count will be considered // including the maximum of leftCount or the rightCount if (root.data == 1) return Math.Max(l, r) + 1; else return Math.Max(l, r); } // Returns maximum count of 1 in any path // in tree with given root static int findMaxCount(Node root) { // Initialize result res = int.MinValue; // Compute and return result countUntil(root); return res; } // Driver program public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(0); root.right = newNode(1); root.left.left = newNode(1); root.left.right = newNode(1); root.left.right.left = newNode(1); root.left.right.right = newNode(0); Console.Write(findMaxCount(root)); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the above approach// A binary tree nodeclass Node { constructor() { this.left = null; this.data = 0; this.right = null; }};var res = 0;// A utility function to allocate a new nodefunction newNode(data){ var newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode);}// This function updates overall count of 1 in 'res'// And returns count 1s going through root.function countUntil(root) { // Base Case if (root == null) return 0; // l and r store count of 1s going through left and // right child of root respectively var l = countUntil(root.left); var r = countUntil(root.right); // maxCount represents the count of 1s when the Node under // consideration is the root of the maxCount path and no // ancestors of the root are there in maxCount path var maxCount; // if the value at node is 1 then its // count will be considered // including the leftCount and the rightCount if (root.data == 1) maxCount = l + r + 1; else maxCount = l + r; // Store the Maximum Result. res = Math.max(res, maxCount); // return max count in a single path. // This path must include at-most one child // of the root as well as itself // if the value at node is 1 // then its count will be considered // including the maximum of leftCount or the rightCount if (root.data == 1) return Math.max(l, r) + 1; else return Math.max(l, r);}// Returns maximum count of 1 in any path// in tree with given rootfunction findMaxCount(root) { // Initialize result res = -1000000000; // Compute and return result countUntil(root); return res;}// Driver programvar root = newNode(1);root.left = newNode(0);root.right = newNode(1);root.left.left = newNode(1);root.left.right = newNode(1);root.left.right.left = newNode(1);root.left.right.right = newNode(0);document.write(findMaxCount(root));</script> |
Output:
4
Time Complexity: O(n)
where n is number of nodes in Binary Tree.
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!
