For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.
Solution:
Do inorder traversal, if current nodes' data is between K1 and K2 (K1<= root->data >= K2) Print it.
Time Complexity : O(log n) + O(k) , where n = no of nodes and k = no of keys printed.
Code:
void printbstkeys(Tnode *root,int k1,int k2) { if(root==NULL) return; printbstKey(root->left, k1, k2); if(root->data >=k1 && root->data <=k2) printf(" %d ",root->data); printbstKey(root->right,k1,k2); return; }
To avoid unwanted traversals we can compare current node's
data with K1 for left subtree and K2 for right subtree.
void printbstkeys(Tnode *root,int k1,int k2) { if(root==NULL) return; if(root->data>=k1) printbstKey(root->left, k1, k2); if(root->data >=k1 && root->data <=k2) printf(" %d ",root->data); if(root->data<k2) printbstKey(root->right,k1,k2); return; }
This comment has been removed by the author.
ReplyDeleteTo increase the efficiency, we can perform a check whether the given range is smaller or larger than root node. In such case we can provide either the left or right child of root as the root node for traversal and going through only left or right sub tree :) :)
ReplyDelete