Description: Given a binary search tree and 2 integers m1 and m2, print all elements that lie between m1 and m2 in the BST in increasing order.

Example:

if m1=8 and m2=12

OUTPUT: 8, 9, 10, 12

Algorithm and Implementation:

In inorder traversal, the order of traversal is

left subtree->root->right subtree.

Since in a BST, the root element is greater than all elements of the left subtree and smaller than all elements of the right subtree INORDER traversal in a BST results in elements being traversed in a increasing sequence.

Since, we want the elements to be printed in an increasing order, we’ll use the inorder traversal.

/*The function below prints BST elements that lie between m1 and m2:*/

void printBSTelement(struct node *root, int m1, int m2)

{

if ( root==NULL )/*empty*/

return;

if (root->data >m1)

printBSTelement(root->left, m1, m2);/*left subtree*/

if ( m1 <= root->data && m2 >= root->data )

PRINT root->data.

if ( m2 > root->data )

printBSTelement(root->right, m1, m2);/*right subtree*/

}

Time Complexity:

O(n), where n is number of nodes in the binary tree.
Go to top