Binary Tree - Naukri Code 360

Introduction

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.

Count Nodes Having the highest value in path from root to itself in a binary tree

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.

Sample Example

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

Input:

Consider the given tree

Output:

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:
1. If the root node is null, return 0.
2. 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.
3. Initialize the count to 0.
4. If the value of the current node is equal to the highest value found so far, increment the count by 1.
5. Recursively count the number of nodes having the highest value in the left and right subtrees.
6. 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.
1. Check if root is nullptr. Since root is not nullptr, proceed to the next step.
2. 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.
3. Initialize count to 0.
4. Check if the value of the current node (3) is equal to max_val (5). Since it is not equal, set count to 0.
5. Recursively call countNodes with root -> left (which is nullptr) and max_val as arguments. This will return 0.
6. Recursively call countNodes with root -> right (which is nullptr) and max_val as arguments. This will return 0.
7. 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.
1. Check if root is nullptr. Since root is not nullptr, proceed to the next step.
2. 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.
3. Check if the value of the current node (8) is equal to max_val (8). Since it is equal, set count to 1.
4. Recursively call countNodes with root -> left (which is nullptr) and max_val as arguments. This will return 0.
  1. Recursively call countNodes with root -> right (which has a value of 10) and max_val as arguments.
  2. Check if root is nullptr. Since root is not nullptr, proceed to the next step.
  3. Check if the value of the current node (10) is greater than max_val (8). Since it is greater, update max_val to 10.
  4. Initialize count to 0.
  5. 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);
    }
}

You can also try this code with Online Java Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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.