Finding the minimum and maximum elements in a binary seach tree

Given a binary search tree, how do we find the maximum and minimum elements in it?

For example in the given tree, the maximum element is 8 and the minimum element is 1.

This algorithm is based on the following simple observation.

In a Binary search tree, the minimum element always lies on the left most node and the maximum element always lies on the right most node.

Here is the simple implementation of this algorithm in C++.

	#include <iostream>
	#include <climits>
	using namespace std;

	class BSTNode
	{
	int data;
	BSTNode *left;
	BSTNode *right;

	public:
	//single param constructor
	BSTNode(int d):data(d), left(NULL), right(NULL)
	{
	}

	BSTNode(int d, BSTNode l, BSTNode r):data(d), left(l), right(r)
	{
	}

	int getData()
	{
	return data;
	}

	void setData(int d)
	{
	data = d;
	}

	BSTNode* getLeft()
	{
	return left;
	}

	void setLeft(BSTNode *l)
	{
	left = l;
	}

	BSTNode* getRight()
	{
	return right;
	}

	void setRight(BSTNode *r)
	{
	right = r;
	}

	};

	class BinarySearchTree
	{
	BSTNode * root;
	public:
	BinarySearchTree():root(NULL)
	{
	}
	BSTNode * getRoot()
	{
	return root;
	}
	bool insert(int d)
	{
	if( root == NULL ) // if tree is empty
	{
	root = new BSTNode(d);
	return true;
	}
	else
	{
	BSTNode *ptr = root;
	BSTNode *prev = NULL;

	while( ptr != NULL )
	{
	prev = ptr;

	if( ptr->getData() == d )//no duplicates allowed in BST
	return false;
	else if( ptr->getData() < d )
	{
	ptr = ptr->getRight();
	}
	else
	{
	ptr = ptr->getLeft();
	}
	}

	if( prev->getData() < d ) //to be added as right child?
	prev->setRight( new BSTNode(d) );
	else
	prev->setLeft( new BSTNode(d) );
	return true;
	}
	}

	//Returns the minimum element; INT_MAX if the tree is empty
	int getMin()
	{
	if( root == NULL )
	return INT_MAX;

	BSTNode *ptr = root;

	while ( ptr->getLeft() != NULL )
	ptr = ptr->getLeft();

	return ptr->getData();
	}
	//Returns the maximum element; INT_MIN if tree it empty
	int getMax()
	{
	if( root == NULL )
	return INT_MIN;

	BSTNode *ptr = root;

	while ( ptr->getRight() != NULL )
	ptr = ptr->getRight();

	return ptr->getData();
	}

	};

	int main()
	{
	BinarySearchTree *bst = new BinarySearchTree();

	bst->insert(5);
	bst->insert(3);
	bst->insert(8);
	bst->insert(4);
	bst->insert(9);
	bst->insert(1);
	bst->insert(10);
	bst->insert(2);
	bst->insert(6);
	bst->insert(7);

	cout<< bst->getMax() << endl;
	cout<< bst->getMin() << endl;

	return 0;
	}

view raw MinMaxBinaryTree.cpp hosted with

by GitHub

Leave a Reply Cancel reply