CareerCup

here is the correct code , i just forget to include the print statemnt

printNodes(Node root,int m,int n)
{
    if(root==null)
     return;
    if(root.data>=m&&root.data<=n)
    print(root.data);
    if(m<root.data)
    printNode(root.left,m,n);
    if(n>root.data)
    printNode(root.right,m,n);
}

How about this? Its short and sweet :P

public static void printRange( Node node, int r1, int r2 ) {
     if(node == null) return;
     if(node.data > r2)
       printRange(node.left, r1, r2);
     if(node.data < r1)
       printRange(node.right, r1, r2);
 
     if(r1 <= node.data && node.data <= r2) {
       System.out.println("Node data: " + node.data);
       printRange(node.right, r1, r2);
       printRange(node.left, r1, r2);
     }
   }

Algo:
1. First find the min
2. Go for inorder
3. Print the nodes between n(smaller) and m(larger)

Hi raiprince001. How did you get the interview with MS bing? Employee Referral? Consultant? or somthing else ? pls reply.

we can do it in O(k + log(z)) time , where k = number of printed nodes (between n and m) and z = total number of nodes in the BST.
say n<m
Like in order
if currval of the node <= n go right
if(currval of the node is in between n and m print)
if currval of the node > m go left

I went through the Employee Referral ..!!

How about this ?

bool ReturnBtw(curr, m, n) {
if(!curr)
return false;

else // find m
{
while(curr->val == m){
if(curr-val > m)
curr = curr->left;
else
curr = curr->right;
}
//found m, stored in m
int flag = true;
Print(curr, flag, n);
}

Print(curr, flag, n){

if(!curr || curr->val == n)
return;

else{
if(flag) {
cout<<curr->right->val;
Print(curr->right, false, n);
}
else{
Print(curr->left, false,n);
cout<<curr->val;
Print (curr->right, false, n);
}
}
}

Idea is, if found m, we need to traverse the immediate right subtree, and after that do the normal inporder traversal, until u reach destination node.

complexity: O(no. of nodes btw m & n)

here is the code

printNodes(Node root,int m,int n)
{
    if(root==null)
     return;
    if(n<root.data)
    printNode(root.left,m,n);
    if(m>root.data)
    printNode(root.right,m,n);
}

@techcoderonwork

Will this really work.....
Check this out for this example...
18
/ \
15 20
/ \ / \
13 16 19 24
The value of m and n are 16 and 30...I think it wont satisfy any if statement

#include<iostream>
#include"BinaryTree.h"

using namespace std;

#define NELEMS(x) (sizeof(arr)/sizeof(arr[0]))

void findNodesInRange(btree *p, int m, int n)
{
        if(n < m)
                return;

        if(p == NULL)
                return;

        if(p->data > n)
                findNodesInRange(p->left, m, n);
        else if(p->data < m)
                findNodesInRange(p->right, m ,n);
        else
        {
                cout << p->data << endl;
                findNodesInRange(p->left, m, p->data);
                findNodesInRange(p->right, p->data, n);
        }
}

int main(int argc, char *argv[])
{
        btree *root = NULL;
        int arr[] = {12,7,4,2,6,10,8,11,9,20,16,14,19,18,24,22,26};

        if(argc != 3)
        {
                cout << "invalid command line usage" << endl;
                return 1;
        }

        for(int i = 0; i < NELEMS(arr); i++)
        {
                root = BinaryTree_insert(root, arr[i]);
        }

        findNodesInRange(root, atoi(argv[1]), atoi(argv[2]));
        return 0;
}

1) Find LCA { Easy to do in O(lg n ) if you have a visited bit with each node in the tree }
2) from LCA print all nodes until we reach m.
3) Print right subtree of m.
4) From LCA print all nodes, until we reach n.
5) Print Left subtree of n.

#include<conio.h>
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node*left;
struct node*right;
};


void insert(struct node**q,int num)
{
struct node *temp=NULL;
temp=(struct node*)malloc(sizeof(struct node));
if(*q==NULL)
{
temp->data=num;
temp->left=NULL;
temp->right=NULL;
*q=temp;
// printf("%d\n",temp->data);
}
else
{
if(((*q)->data)>num)
insert(&((*q)->left),num);
else
insert(&((*q)->right),num);
}
}

void range(struct node *p,int m,int n)
{
if(p==NULL)
return;
else
{
if(m>p->data)
range(p->right,m,n);
else
{
if(n<p->data)
range(p->left,m,n);
else
{
printf("%d\n",p->data);
range(p->left,m,p->data-1);
range(p->right,p->data+1,n);
}
}}
}
int main()
{
struct node*p;
p=NULL;

insert(&p,17);
insert(&p,13);
insert(&p,21);
insert(&p,27);
insert(&p,19);
insert(&p,8);
insert(&p,15);
range(p,10,20);
getch();
return 0;
}

fun(node*n,int m int n))
{ if(n)
{ if(n->data>=m&& n->data<=n)
{ cout<<n->data;
if(n->left)
fun(n->left);
if(n->rite)
fun(n->rite);
}

if(n->data>m)
fun(n->left);
if(n->data<m)
fun(n->rite);
}
}

oops forgot to login.pasting code again.

fun(node*n,int m int n))
{ if(n)
{ if(n->data>=m&& n->data<=n)
{ cout<<n->data;
if(n->left)
fun(n->left);
if(n->rite)
fun(n->rite);
}

if(n->data>m)
fun(n->left);
if(n->data<m)
fun(n->rite);
}
}