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.

 
If video does not load, Click here
 
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