Given a Binary Tree, the task is to count the number of nodes in the Binary Tree, which are the highest valued node in the path from the root up to that node.
Examples:
Input: Below is the given Tree:
3
/ \
2 5
/ \
4 6
Output: 4
Explanation:
Root node satisfies the required condition.
Node 5 is the highest valued node in the path (3 -> 5).
Node 6 is the highest valued node in the path (3 -> 5 -> 6).
Node 4 is the highest valued node in the path (3 -> 2 -> 4).
Therefore, there are a total of 4 such nodes in the given binary tree.Input: Below is the given Tree:
3
/ \
1 2
/ \
4 6
Output: 3
Approach: The idea is to perform Inorder Traversal of the given Binary Tree and update the maximum valued node obtained so far in the path after each recursive call. Follow the steps below:
- Perform Inorder Traversal on the given Binary Tree
- After each recursive call, update the maximum valued node encountered till now in the path from the root node to the current node.
- If the value of the node exceeds the maximum valued node in the path so far, increase the count by 1 and update the maximum value obtained so far.
- Proceed to the subtrees of the current node.
- After complete traversal of the Binary Tree, print the count obtained.
Below is the implementation of the above approach:
C++
// C++14 program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the ct of // nodes which are maximum // in the path from root // to the current node int ct = 0; // Binary Tree Node struct Node { int val; Node *left, *right; Node( int x) { val = x; left = right = NULL; } }; // Function that performs Inorder // Traversal on the Binary Tree void find(Node *root, int mx) { // If root does not exist if (root == NULL) return ; // Check if the node // satisfies the condition if (root->val >= mx) ct++; // Update the maximum value // and recursively traverse // left and right subtree find(root->left, max(mx, root->val)); find(root->right, max(mx, root->val)); } // Function that counts the good // nodes in the given Binary Tree int NodesMaxInPath(Node* root) { // Perform inorder Traversal find(root, INT_MIN); // Return the final count return ct; } // Driver code int main() { /* A Binary Tree 3 / \ 2 5 / \ 4 6 */ Node* root = new Node(3); root->left = new Node(2); root->right = new Node(5); root->left->left = new Node(4); root->right->right = new Node(7); // Function call int answer = NodesMaxInPath(root); // Print the count of good nodes cout << (answer); return 0; } // This code is contributed by mohit kumar 29 |
Java
// Java program for the above approach import java.util.*; class GfG { // Stores the count of // nodes which are maximum // in the path from root // to the current node static int count = 0 ; // Binary Tree Node static class Node { int val; Node left, right; } // Function that performs Inorder // Traversal on the Binary Tree static void find(Node root, int max) { // If root does not exist if (root == null ) return ; // Check if the node // satisfies the condition if (root.val >= max) count++; // Update the maximum value // and recursively traverse // left and right subtree find(root.left, Math.max(max, root.val)); find(root.right, Math.max(max, root.val)); } // Function that counts the good // nodes in the given Binary Tree static int NodesMaxInPath(Node root) { // Perform inorder Traversal find(root, Integer.MIN_VALUE); // Return the final count return count; } // Function that add the new node // in the Binary Tree static Node newNode( int data) { Node temp = new Node(); temp.val = data; temp.left = null ; temp.right = null ; // Return the node return temp; } // Driver Code public static void main(String[] args) { /* A Binary Tree 3 / \ 2 5 / \ 4 6 */ Node root = null ; root = newNode( 3 ); root.left = newNode( 2 ); root.right = newNode( 5 ); root.left.left = newNode( 4 ); root.right.right = newNode( 7 ); // Function Call int answer = NodesMaxInPath(root); // Print the count of good nodes System.out.println(answer); } } |
Python3
# Python 3 program for the # above approach import sys # Stores the ct of # nodes which are maximum # in the path from root # to the current node ct = 0 # Binary Tree Node class newNode: def __init__( self , x): self .val = x self .left = None self .right = None # Function that performs Inorder # Traversal on the Binary Tree def find(root, mx): global ct # If root does not exist if (root = = None ): return # Check if the node # satisfies the condition if (root.val > = mx): ct + = 1 # Update the maximum value # and recursively traverse # left and right subtree find(root.left, max (mx, root.val)) find(root.right, max (mx, root.val)) # Function that counts # the good nodes in the # given Binary Tree def NodesMaxInPath(root): global ct # Perform inorder # Traversal find(root, - sys.maxsize - 1 ) # Return the final count return ct # Driver code if __name__ = = '__main__' : ''' /* A Binary Tree 3 / / 2 5 / / 4 6 */ ''' root = newNode( 3 ) root.left = newNode( 2 ) root.right = newNode( 5 ) root.left.left = newNode( 4 ) root.right.right = newNode( 7 ) # Function call answer = NodesMaxInPath(root) # Print the count of good nodes print (answer) # This code is contributed by Surendra_Gangwar |
C#
// C# program for // the above approach using System; class GfG{ // Stores the count of // nodes which are maximum // in the path from root // to the current node static int count = 0; // Binary Tree Node public class Node { public int val; public Node left, right; } // Function that performs // Inorder Traversal on // the Binary Tree static void find(Node root, int max) { // If root does not exist if (root == null ) return ; // Check if the node // satisfies the condition if (root.val >= max) count++; // Update the maximum value // and recursively traverse // left and right subtree find(root.left, Math.Max(max, root.val)); find(root.right, Math.Max(max, root.val)); } // Function that counts the good // nodes in the given Binary Tree static int NodesMaxInPath(Node root) { // Perform inorder Traversal find(root, int .MinValue); // Return the readonly count return count; } // Function that add the new node // in the Binary Tree static Node newNode( int data) { Node temp = new Node(); temp.val = data; temp.left = null ; temp.right = null ; // Return the node return temp; } // Driver Code public static void Main(String[] args) { /* A Binary Tree 3 / \ 2 5 / \ 4 6 */ Node root = null ; root = newNode(3); root.left = newNode(2); root.right = newNode(5); root.left.left = newNode(4); root.right.right = newNode(7); // Function Call int answer = NodesMaxInPath(root); // Print the count of good nodes Console.WriteLine(answer); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program for the above approach // Stores the count of // nodes which are maximum // in the path from root // to the current node let count = 0; // Binary Tree Node class Node { constructor(data) { this .left = null ; this .right = null ; this .val = data; } } // Function that add the new node // in the Binary Tree function newNode(data) { let temp = new Node(data); // Return the node return temp; } // Function that performs Inorder // Traversal on the Binary Tree function find(root, max) { // If root does not exist if (root == null ) return ; // Check if the node // satisfies the condition if (root.val >= max) count++; // Update the maximum value // and recursively traverse // left and right subtree find(root.left, Math.max(max, root.val)); find(root.right, Math.max(max, root.val)); } // Function that counts the good // nodes in the given Binary Tree function NodesMaxInPath(root) { // Perform inorder Traversal find(root, Number.MIN_VALUE); // Return the final count return count; } // Driver code /* A Binary Tree 3 / \ 2 5 / \ 4 6 */ let root = null ; root = newNode(3); root.left = newNode(2); root.right = newNode(5); root.left.left = newNode(4); root.right.right = newNode(7); // Function Call let answer = NodesMaxInPath(root); // Print the count of good nodes document.write(answer); // This code is contributed by suresh07 </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!