Write a program such that given a BST,return the size of largest subtree that lies within a given range[a,b].

Write a program such that given a BST,return the size of largest subtree that lies within a given range[a,b].

N.B: This  exact question was asked in a Google interview. 

This problem when looked at first looks simple and may be for some it it but for me when it wasn't because when I started coding it I got all confused between recursions and the flow the algorithm will take.So i started simple on pen and paper tried for a couple of hours and could make it work .

Point to be noted here is that the following approach here I took is not the most

 efficient way but yes it does works perfectly.

Steps or rather my thoughts :

I had to touch each node so that I can calculate the size of the subtree in case the tree below and the node itself lied in the range.And after i calculate it I have maintained a global variable that stores the current max and when new value comes it compares it with existing one and updates it with the max value between them.

To do so ,we start BFS and for each node that occurs from BFS pop I process(Return an integer temp ,thats the size if whole subtree including itself lies in range or return 0 if somewhere down below it violated the range)  and compare it with the current max.Then I update max to be maximum of max  and my process result.

So ultimately i get return max which either contains 0 or some Value which was expected from question.

Point to be noted is how I process each node.Its quite tricky how the recursion works.Feel free to comment if you are confused.Below is the working code for above image[range 15-25].

Improvements:
The below code is like the brute force method but while solving it it realised its a case of overlapping sub-problems of dynamic programming as each subtree is processed multiple times and hence can surely be solved using dynamic programming.Working on it.Will update soon :)

package testGoogle;

import java.util.LinkedList;

import java.util.Queue;

class Treenode{

int x;

Treenode  l;

Treenode r;

Treenode(int  data){

x = data;

l = null;

r = null;

};

}

class BST{

Treenode root;

 

    /* Constructor */

    public BST()

    {

        root = null;

    }

public void insert(int data)

    {

        root = insert(root, data);

    }

    /* Function to insert data recursively */

    private Treenode insert(Treenode node, int data)

    {

        if (node == null)

            node = new Treenode(data);

        else

        {

            if (data <= node.x)

                node.l = insert(node.l, data);

            else

                node.r = insert(node.r, data);

        }

        return node;

    }

}

public class testGoog {

static int temp =0;

public static int solution(int A, int B, Treenode T) {

      int max =0;//BFS starts

Queue<Treenode> q =new LinkedList<Treenode>();

q.add(T);

while(!q.isEmpty())

{

Treenode x  = q.poll();

if(x.l != null)

q.add(x.l);

if(x.r != null)

q.add(x.r);

//Each node process the subtree size and set it to max.

//It can either be zero or some value at any point.

max = Math.max(max,process(x,A,B));

//After processing make temp back to 0 so that it can start fresh for

                               //next subtree

temp = 0;

}

        return  max;

    }

 

       private static int process(Treenode n,int a,int b)

{

if (n == null){

return -1;

}

if(n.x>=a && n.x<=b){

temp =temp+1;

int l = process(n.l, a, b);

if(l==0){

temp = 0;

return 0;

}

int r = process(n.r, a, b);

if(r==0){

temp = 0;

return 0;

}

 

}else{

return 0;

}

return temp;

}

 //Main Method to create a tree and test

public static void main(String args[]){

BST tree = new BST();

tree.insert(25);

tree.insert(19);

tree.insert(37);

tree.insert(12);

tree.insert(22);

tree.insert(4);

tree.insert(23);

testGoog finMax = new testGoog();

System.out.println(finMax.solution( 2, 40,tree.root));

 

}

}