Second largest number in binary search tree

Second largest number in binary search tree

In last post : Find minimum and maximum in BST, we learned how to find minimum and maximum node in BST using recursive as well as iterative way. Today’s problem is to find second largest number in BST. Second largest number is such that there is one node which is greater than it. For example in binary search tree below, second largest number will be 40.

find second largest number in BST

Second largest number in binary search tree : Algorithm

First method is to scan through entire tree in inorder way, store it an array and then return last to one element from it. This method requires only one traversal of tree, however, uses extra space to store inorder traversal. Complexity is O(N) in time and O(N) in space.

Second method is to inorder traverse tree twice. First calculate number of nodes in tree, call it n. Now, traverse again and find (n-1)th node. This does not require any additional space, but traverses the tree twice.

One thing, we know for sure that we have to do inorder traversal of BST as it gives us sorted order of nodes and it would be easier to find second largest element in that order. In second method, our concern was that we are traversing tree twice, once to find number of nodes and then to find second largest node.

How about traversing BST inorder but in reverse order, so that it still gives  nodes sorted but in descending order. Then all we need to find is second node in that order. This requires only one traversal of tree and no extra space.

Second largest number in binary search tree : Implementation

Code below is generic code which can find any largest element in BST by setting K correctly.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
void findSecondMaximum( Node * root, int *count, int K ){
	if( !root ) return;
 
	findSecondMaximum(root->right, count, K);
 
	if( ++(*count) == K ){
		printf("\n %dth element in tree : %d", K, root->value);
		return;
	}
	if( *count < K ){
		//Processing left subtree only if count is still less than K
		findSecondMaximum(root->left, count, K);
	}
} 
 
void inorderTraversal(Node * root){
	if(!root)
		return;
 
	inorderTraversal(root->left);
	printf("%d ", root->value);
	inorderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value){
	if(!node){
		return createNode(value);
	}
	if (node->value > value)
		node->left = addNode(node->left, value);
	else
		node->right = addNode(node->right, value );
 
	return node;
}
 
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root, 30);
	root = addNode(root, 20);
	root = addNode(root, 15);
	root = addNode(root, 25);
	root = addNode(root, 40);
	root = addNode(root, 38);
	root = addNode(root, 45);
	printf("\nInorder traversal of tree is : ");
	inorderTraversal(root);
	printf("\n");
	int count = 0;
	int K = 2;
	findSecondMaximum(root, &count, K);
 
	return 0;
}

Complexity of finding second largest elements still remains O(N) as in skewed binary search trees, we may have to traverse n-1 nodes.

Please share if something is wrong or missing in this post. Sharing is caring.