Approach
We will traverse the tree recursively to find the number of nodes with values greater than K. We will be building two functions:
- countNodesGreaterThanK(currentNode, K) - It will count the total number of nodes greater than K in the tree rooted at the current node.
- countNodes(currentNode) - It will calculate the total number of nodes in the tree rooted at the current node.
While traversing in the first function, we will encounter these 3 cases:
-
Value at the current node is equal to K - So we know all the nodes on the right of this node will be greater than X. Therefore -
countNodesGreaterThanK(currentNode, K) = countNodes(currentNode->right)
-
Value at the current node is greater than K - So we know all the nodes on the right of this node, including the current node will be greater than K. But we can’t say the same for the left subtree so that we will traverse recursively in the left subtree.
countNodesGreaterThanK(currentNode, K) = countNodes(currentNode->right) + 1 + countNodesGreaterThanK(currentNode->left,K)
-
Value at the current node is smaller than K - So we know all the nodes on the left of this node will be smaller than K. So we can move on the right of this node.
countNodesGreaterThanK(currentNode, K) = countNodesGreaterThanK(currentNode->right,K)
Code in C++
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
class AVLTreeNode{
public:
int key;
int height;
AVLTreeNode *left,*right;
AVLTreeNode(int key){
this->key = key;
height = 1;
left = right = NULL;
}
void updateHeight();
};
int getHeight(AVLTreeNode* head){
if(head==NULL){
return 0;
}else{
return head->height;
}
}
void AVLTreeNode::updateHeight(){
this->height = max(getHeight(left),getHeight(right))+1;
}
AVLTreeNode* rightRotation(AVLTreeNode* head){
/*
head y
/ \ / \
y y2 x head
/ \ ----> / \ / \
x x2 z1 z2 x2 y2
/ \
z1 z2
*/
AVLTreeNode* y = head->left;
AVLTreeNode* x = y->left, *x2 = y->right;
// Updating the pointers of the nodes
y->right = head;
head->left = x2;
// Now update the height too of the nodes
head->updateHeight();
y->updateHeight();
return y;
}
AVLTreeNode* leftRotation(AVLTreeNode* head){
/*
head y
/ \ / \
y2 y head x
/ \ ----> / \ / \
x2 x y2 x2 z1 z2
/ \
z1 z2
*/
AVLTreeNode *y = head->right;
AVLTreeNode *x = y->right, *x2 = y->left;
y->left = head;
head->right = x2;
// Now update the height too of the nodes
head->updateHeight();
y->updateHeight();
return y;
}
int getBalance(AVLTreeNode* head){
if(head==NULL){
return 0;
}
return getHeight(head->left) - getHeight(head->right);
}
AVLTreeNode* insertRecursively(AVLTreeNode* head,int key){
AVLTreeNode* new_node = new AVLTreeNode(key);
if(head==NULL){
return new_node;
}
if(key<head->key){
head->left = insertRecursively(head->left,key);
}else{
head->right = insertRecursively(head->right,key);
}
// Update the height of the head
head->updateHeight();
if(getBalance(head)==2 && getBalance(head->left)==1){
// left left rotation
return rightRotation(head);
}
else if(getBalance(head)==-2 && getBalance(head->right)==-1){
// right right rotation
return leftRotation(head);
}else if(getBalance(head)==-2 && getBalance(head->right)==1){
// right left rotation
head->right = rightRotation(head->right);
return leftRotation(head);
}else if(getBalance(head)==2 && getBalance(head->left)==-1){
// left right rotation
head->left = leftRotation(head->left);
return rightRotation(head);
}
return head;
}
int countNodes(AVLTreeNode* root){
if(root==NULL){
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
void preOrderTraversal(AVLTreeNode* root){
if(root==NULL){
return;
}
cout<<root->key<<" ";
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
int countNodesGreaterThanK(AVLTreeNode* root,int K){
if(root==NULL){
return 0;
}
if(root->key==K){
return countNodes(root->right);
}else if(root->key>K){
int sum = countNodes(root->right)+1;
sum += countNodesGreaterThanK(root->left,K);
return sum;
}else{
return countNodesGreaterThanK(root->left,K);
}
}
int main(){
// Constructing the AVL Tree
AVLTreeNode* root = NULL;
root = insertRecursively(root, 10);
root = insertRecursively(root, 20);
root = insertRecursively(root, 30);
root = insertRecursively(root, 40);
root = insertRecursively(root, 50);
root = insertRecursively(root, 25);
/*
30
/ \
20 40
/ \ \
10 25 50
*/
cout<<"Pre-order traversal of the above AVL Tree is : "<<endl;
preOrderTraversal(root);
cout<<endl;
cout<<"The total number of nodes with a value greater than 20 in the tree is "<<countNodesGreaterThanK(root,20)<<endl;
}
You can also try this code with Online C++ Compiler
Output
Pre-order traversal of the above AVL Tree is :
30 20 10 25 40 50
The total number of nodes with a value greater than 20 in the tree is 4
Time Complexity
Since we traverse the tree only once, the time complexity is O(N), where N = the total number of nodes in the AVL Tree.
Space Complexity
We are using recursion; therefore, the recursive stack will take some space. The space complexity due to the recursive stack will be O(height) = O(log N), where N = the total number of nodes in the AVL Tree.
Frequently Asked Questions
1.What is the time complexity of the insert, delete, and search operations in an AVL tree?
The time complexity of these operations is O(log N), where N is the number of nodes in the red-black tree.
2.What is the difference between a red-black tree and an AVL tree?
The main difference between an AVL tree and a red-black tree is that the AVL trees are more balanced than a red-black tree. But insert and delete operations are costly in the case of AVL trees as we may require some rotations to perform insert and delete operations. Therefore we should prefer red-black trees if insertion and delete operations are more. We should prefer AVL trees if the search is a more frequent operation.
3.Are there more problems on Coding Ninjas Studio that deal with Data Structures and Algorithms?
Yes, Coding Ninjas Studio allows you to practice coding and offers frequently asked interview questions. The more we practice, the more our chances of landing a job at our ideal organization.
Key Takeaways
In this article, we learned to find the number of nodes greater than K in an AVL in the most efficient way. Since data structures and algorithms are frequently asked in interviews, we recommend you practice more problems on Coding Ninjas Studio.
Check out this problem - Connect Nodes At Same Level
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!
34+ registered 
