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

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*/



  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