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

Problem Statement

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

Some examples

Examples 1: 

Input: Consider the given tree

 

Output: 5

Explanation: 

The root node is the highest value in its path.

Node 2 is the highest value in the path from root to itself(1->2)

Similarly, 

Node 3 (1->3)

Node 4 (1->2->4)

Node 5 (1->2->5)

So in this way, the total count of nodes in the given Binary tree which satisfies the given condition would be 5.

 

Example 2:

Input: Consider the given Binary tree

 

Output: 3

Explanation: 

The root node is the highest value in its path initially.

Node 7 (5->7)

Node 6(5->2->6)

Approach

The idea of solving the problem would be something like that, first of all, finding the Inorder traversal of a given Binary Tree. We will find the maximum value available for each traversal and update that value after every call.

 

Steps for the given approach:

  1. First, we will perform the inorder traversal for the given Binary Tree.
  2. After every recursive call, we will update the maximum valued node in the path side by side.
  3. If the current node value is greater than the values obtained, update the maximum value and increase the count by one.
  4. Follow the above steps till we reach the last leaf nodes.
  5. Print total counts of nodes present in the given Binary Tree having the highest value from node to itself.

 

Inorder Traversal for Binary Tree:

In this type of traversal in Binary Tree, we first iterate through all the nodes of the left subtree, then the root node, and at last the right subtree.

Pseudo Code for Inorder Traversal:

void Inorder(Node *root)
{
     if(root==NULL)
     return;


     Inorder(root->left); // Left Subtree Recursive call
     cout<<root->data<<" "; // Root Node
     Inorder(root->right); // Right Subtree Recursive call
}

 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    Node *left, *right;   
    Node(int x)
    {
        data = x;
        left = right = NULL;
    }
};

//Inorder Traversal of Binary Tree
void inorder(Node *root, int val,int &count)           
{
    if(root == NULL) // If root does not exist
    return;
     
//If given node satisfies our condition increment the count variable

    if (root->data >= val)                
        count++;
/*
   Recursively call left subtree and right subtree and update the  
   val to choose the highest value during traversal      
*/
    inorder(root->left, max(val, root->data),count);            
    inorder(root->right, max(val, root->data),count);      
}
 
int countNodes(Node* root)
{
    int count=0;
//Inorder Traversal of Binary Tree and initialize the value to a minimum 
    inorder(root, INT_MIN,count);   


//Returning final count of a total of desired such nodes.                                 
    return count;             
}
 
int main()
{
    Node* root = new Node(5); //Insert nodes in the Binary Tree
    root->left = new Node(7);
    root->right = new Node(2);
    root->left->left = new Node(4);
    root->right->right = new Node(6);
     
/*
   Function to count the nodes having the highest value from root to itself     
   in its path 
*/
    int result = countNodes(root);    
     
//Print the total number of nodes in the path as the final answer.
    cout << result;       
    return 0;
}

 

Input: 

 

Output:

3

 

Complexity Analysis

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.

Frequently asked questions

Q1: Which nodes are all the nodes along the path from the root to the node?

Ans: Let’s understand this with an example B, C and D are children of A, while A is the parent of B, C, and D. are siblings. The ancestors of a node are all the nodes along the path from the root to that node.

 

Q2: What is the maximum possible path length in a binary search tree containing n nodes?

Ans: If there are n nodes in a binary search tree, the maximum height of the binary search tree is n-1.

 

Q3: How do you find the best path in a binary tree?

Ans: For each node, there can be four ways that the max path goes through the node:

  1. A path through the only node.
  2. Max path through Left Child + Node.
  3. Max path through Right Child + Node.
  4. Max path through Left Child + Node + Max path through Right Child.

Key Takeaways

This article discussed the fundamental C++ approach, with linear time and space complexity of Count nodes having the highest value in the path from the root to itself in the Binary Tree problem.

If you are a beginner, interested in coding, and want to learn DSA and explore many other concepts, you can look for our free guided path to DSA for reference.

In case of any comments or suggestions, feel free to post them in the comments section.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think