Given the root of a tree, the task is to find the count of nodes which are greater than all of its ancestors.
Examples:
Input: 4 / \ 5 2 / \ 3 6 Output: 3 The nodes are 4, 5 and 6. Input: 10 / \ 8 6 \ \ 3 5 / 1 Output: 1
Approach: The problem can be solved using dfs. In every function call, pass a variable maxx which stores the maximum among all the nodes traversed so far, and every node whose value is greater than maxx is the node that satisfies the given condition. Hence, increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure for the node of the treestruct Tree { int val; Tree* left; Tree* right; Tree(int _val) { val = _val; left = NULL; right = NULL; }};// Dfs Functionvoid dfs(Tree* node, int maxx, int& count){ // Base case if (node == NULL) { return; } else { // Increment the count if the current // node's value is greater than the // maximum value in it's ancestors if (node->val > maxx) count++; // Left traversal dfs(node->left, max(maxx, node->val), count); // Right traversal dfs(node->right, max(maxx, node->val), count); }}// Driver codeint main(){ Tree* root = new Tree(4); root->left = new Tree(5); root->right = new Tree(2); root->right->left = new Tree(3); root->right->right = new Tree(6); // To store the required count int count = 0; dfs(root, INT_MIN, count); cout << count; return 0;} |
Java
// Java implementation of the approachclass GFG{static int count;// Structure for the node of the treestatic class Tree{ int val; Tree left; Tree right; Tree(int _val) { val = _val; left = null; right = null; }};// Dfs Functionstatic void dfs(Tree node, int maxx){ // Base case if (node == null) { return; } else { // Increment the count if the current // node's value is greater than the // maximum value in it's ancestors if (node.val > maxx) count++; // Left traversal dfs(node.left, Math.max(maxx, node.val)); // Right traversal dfs(node.right, Math.max(maxx, node.val)); }}// Driver codepublic static void main(String[] args){ Tree root = new Tree(4); root.left = new Tree(5); root.right = new Tree(2); root.right.left = new Tree(3); root.right.right = new Tree(6); // To store the required count count = 0; dfs(root, Integer.MIN_VALUE); System.out.print(count);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the # above approachfrom collections import deque# A Tree nodeclass Tree: def __init__(self, x): self.val = x self.left = None self.right = Nonecount = 0# Dfs Functiondef dfs(node, maxx): global count # Base case if (node == None): return else: # Increment the count if # the current node's value # is greater than the maximum # value in it's ancestors if (node.val > maxx): count += 1 # Left traversal dfs(node.left, max(maxx, node.val)) # Right traversal dfs(node.right, max(maxx, node.val)) # Driver codeif __name__ == '__main__': root = Tree(4) root.left = Tree(5) root.right = Tree(2) root.right.left = Tree(3) root.right.right = Tree(6) # To store the required # count count = 0 dfs(root, -10 ** 9) print(count)# This code is contributed by Mohit Kumar 29 |
C#
// C# implementation of the approachusing System;class GFG{static int count;// Structure for the node of the treepublic class Tree{ public int val; public Tree left; public Tree right; public Tree(int _val) { val = _val; left = null; right = null; }};// Dfs Functionstatic void dfs(Tree node, int maxx){ // Base case if (node == null) { return; } else { // Increment the count if the current // node's value is greater than the // maximum value in it's ancestors if (node.val > maxx) count++; // Left traversal dfs(node.left, Math.Max(maxx, node.val)); // Right traversal dfs(node.right, Math.Max(maxx, node.val)); }}// Driver codepublic static void Main(String[] args){ Tree root = new Tree(4); root.left = new Tree(5); root.right = new Tree(2); root.right.left = new Tree(3); root.right.right = new Tree(6); // To store the required count count = 0; dfs(root, int.MinValue); Console.Write(count);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approachlet count=0;// Structure for the node of the treeclass Tree{ constructor(val) { this.val=val; this.left=this.right=null; }}// Dfs Functionfunction dfs(node,maxx){ // Base case if (node == null) { return; } else { // Increment the count if the current // node's value is greater than the // maximum value in it's ancestors if (node.val > maxx) count++; // Left traversal dfs(node.left, Math.max(maxx, node.val)); // Right traversal dfs(node.right, Math.max(maxx, node.val)); }}// Driver codelet root = new Tree(4);root.left = new Tree(5);root.right = new Tree(2);root.right.left = new Tree(3);root.right.right = new Tree(6);// To store the required countcount = 0;dfs(root, Number.MIN_VALUE);document.write(count);// This code is contributed by unknown2108</script> |
Output
3
Time Complexity: O(N) where N is the number of nodes in given binary tree.
Space Complexity: O(h) where h is the height of binary tree due to stack recursion call.
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!
