Binary Tree is one of the most widely used data structures in computer science. It is a tree data structure in which each node has at most two children, which are referred to as left child and right child.

In a Binary Tree, the path from the root node to any other node is unique. One of the interesting problems that can be solved on Binary Trees is counting the number of nodes having the highest value in the path from the root to itself.

Problem Statement

We are given a Binary tree. Our task is to count the number of nodes in the tree that are of the highest value from the root to that node itself.

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

Sample Example

Let's take a simple example to understand the problem statement better.

Input:

Consider the given tree

Output:

3

Explanation:

The root node 5 is the highest value in its path from the root to itself. (count = 1)

Node 2 has the value 3, which is less than the root node value of 5. Therefore, node 2 cannot be included in the count.

Node 3 has the value 3, which is less than the root node value of 5. Therefore, node 3 cannot be included in the count.

Node 4 has the value 1, which is less than the root node value of 5. Therefore, node 4 cannot be included in the count.

Node 5 has the value 8, which is greater than the root node value of 5. Therefore, node 5 is included in the count.(count = 2)

Node 6 has the value 10, which is greater than the root node value of 5. Therefore, node 6 is included in the count.(count = 3)

So the total count of nodes having the highest value in the path from the root to itself is 3, which are root itself, nodes 5 and 6.

Approach

The idea is to go down in the tree along with the maximum value found, and check for each node whether it is greater than the coming maximum or not.

Algorithm

Define a binary tree node with a value and two children.

Define a recursive function to count nodes having the highest value in the path from the root to itself:

If the root node is null, return 0.

If the value of the current node is greater than the highest value found so far, update the highest value to be the value of the current node.

Initialize the count to 0.

If the value of the current node is equal to the highest value found so far, increment the count by 1.

Recursively count the number of nodes having the highest value in the left and right subtrees.

Return the total count of nodes having the highest value in the path from the root to itself.

Create a binary tree

Set the highest value to be the value of the root node.

Call the recursive function to count nodes having the highest value in the path from the root to itself, passing in the root node and highest value as arguments.

Print the total count of nodes having the highest value in the path from the root to itself.

Dry Run

Now, Let's have the dry run for the same example.

Set max_val to be the value of the root node, which is 5.

Call the countNodes function with root and max_val as arguments.

Check if root is nullptr. Since root is not nullptr, proceed to the next step.

Check if the value of the current node (5) is greater than max_val (5). Since they are equal, skip to the next step.

Initialize count to 0.

Check if the value of the current node (5) is equal to max_val (5). Since they are equal, set count to 1.

Recursively call countNodes with root -> left and max_val as arguments.

Check if root is nullptr. Since root is not nullptr, proceed to the next step.

Check if the value of the current node (3) is greater than max_val (5). Since it is not greater, skip to the next step.

Initialize count to 0.

Check if the value of the current node (3) is equal to max_val (5). Since it is not equal, set count to 0.

Recursively call countNodes with root -> left (which is nullptr) and max_val as arguments. This will return 0.

Recursively call countNodes with root -> right (which is nullptr) and max_val as arguments. This will return 0.

Return the total count of nodes having the highest value in the path from the root to itself, which is count (0) + count (0) + 1 = 1.

Recursively call countNodes with root -> right and max_val as arguments.

Check if root is nullptr. Since root is not nullptr, proceed to the next step.

Check if the value of the current node (8) is greater than max_val (5). Since it is greater, update max_val to 8. Initialize count to 0.

Check if the value of the current node (8) is equal to max_val (8). Since it is equal, set count to 1.

Recursively call countNodes with root -> left (which is nullptr) and max_val as arguments. This will return 0.

Recursively call countNodes with root -> right (which has a value of 10) and max_val as arguments.

Check if root is nullptr. Since root is not nullptr, proceed to the next step.

Check if the value of the current node (10) is greater than max_val (8). Since it is greater, update max_val to 10.

Initialize count to 0.

Check if the value of the current node (10) is equal to.

Implementation in Java

class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
left = null;
right = null;
}
}
class Solution {
// A recursive function to count nodes having the highest value in the path from the root to itself
public static int countNodes(Node root, int max_val) {
// If the root node is null, there are no nodes to count, so we return 0
if (root == null) {
return 0;
}
// If the value of the current node is greater than the highest value found so far,
// we update the highest value to be the value of the current node
if (root.val > max_val) {
max_val = root.val;
}
// Initialize the count to 0
int count = 0;
// If the value of the current node is equal to the highest value found so far,
// increment the count by 1
if (root.val == max_val) {
count = 1;
}
// Recursively count the number of nodes having the highest value in the left and right subtrees
count += countNodes(root.left, max_val);
count += countNodes(root.right, max_val);
// Return the total count of nodes having the highest value in the path from the root to itself
return count;
}
public static void main(String[] args) {
// Create a binary tree with the given example
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(8);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.right = new Node(10);
// Set the highest value to be the value of the root node
int max_val = root.val;
// Call the recursive function to count nodes having the highest value in the path from the root to itself
int count = countNodes(root, max_val);
// Print the total count of nodes having the highest value in the path from the root to itself
System.out.println("Number of nodes having the highest value in the path from the root to itself: " + count);
}
}

Output

Implementation in C++

#include <iostream>
using namespace std;
// Define a binary tree node with a value and two children
struct Node {
int val;
Node *left, *right;
Node(int x) : val(x), left(nullptr), right(nullptr) {}
};
// A recursive function to count nodes having the highest value in the path from the root to itself
int countNodes(Node* root, int max_val) {
// If the root node is null, there are no nodes to count, so we return 0
if (root == nullptr) {
return 0;
}
// If the value of the current node is greater than the highest value found so far,
// we update the highest value to be the value of the current node
if (root->val > max_val) {
max_val = root->val;
}
// Initialize the count to 0
int count = 0;
// If the value of the current node is equal to the highest value found so far,
// increment the count by 1
if (root->val == max_val) {
count = 1;
}
// Recursively count the number of nodes having the highest value in the left and right subtrees
count += countNodes(root->left, max_val);
count += countNodes(root->right, max_val);
// Return the total count of nodes having the highest value in the path from the root to itself
return count;
}
int main() {
// Create a binary tree with the given example
Node *root = new Node(5);
root->left = new Node(3);
root->right = new Node(8);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right->right = new Node(10);
// Set the highest value to be the value of the root node
int max_val = root->val;
// Call the recursive function to count nodes having the highest value in the path from the root to itself
int count = countNodes(root, max_val);
// Print the total count of nodes having the highest value in the path from the root to itself
cout << "Number of nodes having the highest value in the path from the root to itself: " << count << endl;
return 0;
}

Output

Time Complexity

We visit every node once in the given Binary Tree to find the highest value in its path from the root node, so the time complexity is O(N).

Space Complexity

It is O(N) as we are using a recursive stack that can go up to N in case of a skewed binary tree.

Frequently Asked Question

What is a binary tree?

A binary tree is a data structure in which each node can have at most two children, known as the left child and right child.

What is the highest value in the path from the root to a node in a binary tree?

The highest value in the path from the root to a node in a binary tree is the maximum value of all the nodes in the path from the root to that node.

How do you count nodes having the highest value in the path from the root to itself in a binary tree?

You can count nodes having the highest value in the path from the root to itself in a binary tree by recursively traversing the tree and keeping track of the highest value seen so far. If a node has the highest value seen so far, increment the count by 1.

What is the time complexity of counting nodes having the highest value in the path from the root to itself in a binary tree?

The time complexity of counting nodes having the highest value in the path from the root to itself in a binary tree is O(n), where n is the number of nodes in the tree.

How do you implement counting nodes having the highest value in the path from the root to itself in a binary tree in code?

You can implement counting nodes having the highest value in the path from the root to itself in a binary tree using a recursive function that takes the root node and the highest value is seen so far as input.

Conclusion

In conclusion, we have seen how to solve the problem of counting nodes having the highest value in the path from the root to itself in a binary tree using a recursive approach with linear time and space complexity in C++ and Java. If you want to learn more, then check out our articles.

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!

Live masterclass

Master Python: Discover how PhonePe uses your UPI data

by Ashwin Goyal, Product @ Udaan

28 Jun, 2024

01:30 PM

Roadmap to SDE career at Amazon

by Anubhav Sinha, SDE2 @ Amazon

25 Jun, 2024

01:30 PM

Roadmap to becoming Data Expert at MAANG

by Abhishek Soni, Data Scientist @ Amazon

26 Jun, 2024

01:30 PM

Master Python: Discover how PhonePe uses your UPI data