Thread: Find numbers in binary search tree

you are given a binary search tree and a number k.
now write an algorithm that that gives all pairs of nodes p and q in the tree such that p+q=k.

for this i will write a java program..........
here wht my idea is first i will construct a binarysearch tree with the given values and then i will traverse that tree in inorder to get the ascending list of elements and i will store it in an array then i willwrite for loop to determine the pair of numbers which give the sum as given number.......................
import java.io.*;
//int a[]=new int[10];
//int t=0;
class node
{
int info;
node ls,rs;
node()
{
ls=rs=null;
}
}
class BSTREC2combi
{
static int a[]=new int[10];
static int t=0;
static node recbst(node r,int ele)
{
if(r==null)
{
r=new node();
r.info=ele;

}
else
if(ele<r.info)
{
r.ls=recbst(r.ls,ele);
}
else
{
r.rs=recbst(r.rs,ele);
}
return r;
}
static void inorder(node r)
{
if(r!=null)
{
inorder(r.ls);
System.out.println(r.info);
a[t]=r.info;
t++;
inorder(r.rs);
}
}

public static void main(String args[])throws IOException
{
System.out.println("enter no ofelements");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s;
s=br.readLine();
int n=Integer.parseInt(s);
node r=null;
node p=null;
System.out.println("enter elements");
// int a[]=new int[n];
for(int i=1;i<=n;i++)
{
s=br.readLine();
int ele=Integer.parseInt(s);
r=recbst(r,ele);
}
System.out.println("elements in ascending redr atre");
inorder(r);
System.out.println("enter elemnt to bechecked to find pair of numbers");
s=br.readLine();
int k=Integer.parseInt(s);
System.out.println("those numbers are");
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{

if(k==(a[i]+a[j]))
System.out.println(a[i]+" "+a[j]);

}
}





}

Use 2 stacks for iterative inorder and reverse inorder traversal and solve the problem in the same way as for a sorted array.

Avi
Avi Dullu&#039;s Code Arena

can't we convert the binary search tree into a doubly linked list (which is O(n) inplace i suppose)... then we can take two pointers 1 at end and one at the beginning.... then do it the same way.. complete O(n) with constant space :O

can any 1 tell the algo for converting bst to Dll ??