Count nodes having highest value in the path from root to itself in a Binary Tree

0 0 6 minutes read

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>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

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 zambiatek!