Sorry by mistake i write that
Actually I am not getting desired output..
On Mon, Sep 3, 2012 at 11:02 AM, manish untwal wrote:
> if u r getting desired output ? then what is the problem?
>
>
> On Sun, Sep 2, 2012 at 7:24 PM, shubham jain wrote:
>
>> Hi
>> I am trying to convert the BST t
if u r getting desired output ? then what is the problem?
On Sun, Sep 2, 2012 at 7:24 PM, shubham jain wrote:
> Hi
> I am trying to convert the BST to doubly linked list but I am getting
> desired output with this code Plz correct this code.
>
> #include
> #include
> typedef struct tree
And also your solution prints the root to leaf path that sums up to X. But
the path may not contain root as well as leaf also. May be some
intermediate 4 nodes (from root to leaf path)sums up to X. Your code doesnt
provide the solution for that scenario.
On Fri, Nov 11, 2011 at 2:53 PM, aniket cha
As far as I understand, your solution will always contain the path that
essentially start from root. But the actual problem states that the path
may not necessarily start from root.
On Fri, Nov 11, 2011 at 1:21 PM, UTKARSH SRIVASTAV
wrote:
>
> correct me if I am wrong
>
> #include
>
> struct node
correct me if I am wrong
#include
struct node
{
int data;
struct node *left;
struct node * right;
}*root;
int sum(int s,struct node *p,int ar[],int l)
{
if(p == NULL )
{
return 0;
}
if(p->left == NULL && p->right == NULL)
{
if( s - p->data == 0)
Write a recursive function that will store each root to leaf path in an
array. Now for each root to leaf path find the subarray which sums up to X.
On Thu, Nov 10, 2011 at 11:53 PM, AMAN AGARWAL wrote:
> Hi All,
>
> Please give me the solution of this problem.
>
> A binary tree and a number X is
Do a BFS of the tree, keep a separator to masrk where a level ends.. create
the linklist for every level.
On Wed, Sep 21, 2011 at 6:00 PM, prasanth n wrote:
> Given a binary search tree, design an algorithm which creates a linked list
> of all the nodes at each depth (i.e., if you have a tree wi
take countr to be a static variable ... that shud do the job ...!!
btw ...if thats nt the case ... thn i m nt pretty sure wat u are asking to
be done ...
On Sun, Jul 31, 2011 at 2:12 AM, Rahul Mittal wrote:
> help me with this
> we need to find out how many times a function is recursively called
Do u mean something like level order traversal??
On Sat, Jul 30, 2011 at 12:11 PM, saurabh singh wrote:
> please give an example.
>
>
> On Sat, Jul 30, 2011 at 12:10 PM, Mani Bharathi
> wrote:
>
>> connect all sibling nodes of a binary search tree
>>
>> --
>> You received this message becau
please give an example.
On Sat, Jul 30, 2011 at 12:10 PM, Mani Bharathi wrote:
> connect all sibling nodes of a binary search tree
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https:/
Check this
http://ideone.com/o8gF2
On Wed, Jun 29, 2011 at 10:28 PM, Swathi wrote:
> This should be very simple... follow inorder..
>
> Inorder(Node* node, int counter, int N)
> {
> if(node == null)return;
> Inorder(node->left, counter, N);
> counter++;
> if(counter == N)
> {
> print(node
This should be very simple... follow inorder..
Inorder(Node* node, int counter, int N)
{
if(node == null)return;
Inorder(node->left, counter, N);
counter++;
if(counter == N)
{
print(node->data);
return;
}
Inorder(node->right, counter, N);
}
On Wed, Jun 29, 2011 at 9:03 PM, piyush kapo
Order Statistics Tree
On Wed, Jun 29, 2011 at 8:15 PM, sunny agrawal wrote:
> At each node if we store the Number of nodes in the left subtree.we can
> find kth smallest in O(lgn)
> else do a inorder traversal for k nodes
>
> On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal <
> mittal.nishan..
At each node if we store the Number of nodes in the left subtree.we can
find kth smallest in O(lgn)
else do a inorder traversal for k nodes
On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal
wrote:
> how to find kth smallest element in BST...
>
> --
> You received this message because you are su
http://mukeshiiitm.wordpress.com/2010/04/07/finding-kth-smallest-element-in-binary/
I think this solves the problem :)
Rajeev
On Wed, Jun 29, 2011 at 8:07 PM, Nishant Mittal
wrote:
> how to find kth smallest element in BST...
>
> --
> You received this message because you are subscribed to the
Balance the tree and return the Root.
On Sun, Jun 19, 2011 at 12:10 AM, hary rathor wrote:
> then you can use iterative method instead of recursion ...
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send em
then you can use iterative method instead of recursion ...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@
if no recursion and extra space is allowed??
On Sat, Jun 18, 2011 at 11:20 PM, Vipul Kumar wrote:
> traverse the BST , get the count of no. of nodes . now inorder
> traverse again till n/2 . and print that node
>
> On Sat, Jun 18, 2011 at 11:18 PM, Akshata Sharma
> wrote:
> > How to find median
traverse the BST , get the count of no. of nodes . now inorder
traverse again till n/2 . and print that node
On Sat, Jun 18, 2011 at 11:18 PM, Akshata Sharma
wrote:
> How to find median of a Binary Search Tree without storing it in a linear
> data structure by in-order traversal?
>
> --
> You rec
On Thu, Nov 25, 2010 at 11:05 PM, mo...@ismu wrote:
>
> node *bst_to_dl(root)
> {
> node *head1=NULL,head2=NULL,*temp=NULL;
> temp=(node *)calloc(1,sizeof(node));
> temp->value=root->value;
> if(root-left)
> head1=bst_to_dl(root-left);
> if (root->right)
> head2=bst_to_dl(root
node *bst_to_dl(root)
{
node *head1=NULL,head2=NULL,*temp=NULL;
temp=(node *)calloc(1,sizeof(node));
temp->value=root->value;
if(bst-left)
head1=bst_to_dl(root-left);
if (bst->right)
head2=bst_to_dl(root->right);
if(head2&&head1)//root having two children
{
head1->next=h
If BST is stored in an array, which is already in level order, then there is
nothing much remaining to do.
On Wed, Nov 24, 2010 at 9:05 PM, vamsee marpu wrote:
> Hi,
>
>
> Can anybody help me in solving the following problem:
>
>
> Convert a binary search tree in to a doubly linked list in level
oh ya thanks now i got it
On Sun, Oct 24, 2010 at 9:54 AM, preetika tyagi wrote:
> @Praveen- In this case, we will not ignore the right subtree of the root
> (-10, which is less than zero) while traversing the tree.
>
>
> On Sat, Oct 23, 2010 at 9:06 PM, Praveen Baskar
> wrote:
>
>> i think it i
@Praveen- In this case, we will not ignore the right subtree of the root
(-10, which is less than zero) while traversing the tree.
On Sat, Oct 23, 2010 at 9:06 PM, Praveen Baskar wrote:
> i think it is possible nishaanth
> please do take a look at this example
>
> -10
>
i think it is possible nishaanth
please do take a look at this example
-10
/\
-11 8
/\
-5 10
-5 is greater than -10
On Sat, Oct 23, 2010 at 11:19 PM, nishaanth wr
@Praveenit is not possible..in a BST *all the nodes* on the right
subtree are greater than the node :)
On Sat, Oct 16, 2010 at 3:26 PM, Praveen Baskar wrote:
> @nishaanth: wat if the left child of the right node has a negative value
>
> On Thu, Oct 14, 2010 at 11:12 AM, nishaanth wrote:
>
>>
@nishaanth: wat if the left child of the right node has a negative value
On Thu, Oct 14, 2010 at 11:12 AM, nishaanth wrote:
>
>
>> Just see the value of the node at every point, if it is greater than zero
> dont recurse the right sub-tree, as simple as it is.print the node u
> inspected if it is
>
> Just see the value of the node at every point, if it is greater than zero
dont recurse the right sub-tree, as simple as it is.print the node u
inspected if it is less than zero.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are sub
4th element of inorder traversal
On Fri, Oct 8, 2010 at 11:49 PM, Anand wrote:
> Binary search Tree was given. Find 4ths smallest element.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algo
@Manjunath : We can't assume the structure of BST has parent pointers , if
that is explicitly mentioned , then we will have to keep in mind two
pointers one for inorder successor in the left subtree and another for
inorder predecessor in the right subtree and traverse the pointers to find
the
@priyanka i agree with u... but wat i thot was if v had a tree with
parent pointers...we can have one pointer at the left most and another at
the rightmost subtree respectivelyand move along the pointers..
I need ur discussion on thisi think the implementation wud be
difficult..convert
@algoboy:
If you want to use extra space go with sharad's algo: do inorder traversal
, store in a buffer and use 2 pointer method. T(n) =O(n) , S(n)=O(n)
If you don't want to use extra space , convert BST into circular DLL or DLL
and use 2 pointer algorithm. (conversion of BST into DLL is a
typo!
floor(n/2/+1) ==> floor((n/2/+1)/2)
.
Satya
On Fri, Aug 6, 2010 at 5:27 PM, Satya wrote:
> u need to write a recursive function.
> All leaf nodes in complete BST are from n/2+1n.
> n/2+1 element will be the beginning element(least left child) for our
> resultant sorted array
u need to write a recursive function.
All leaf nodes in complete BST are from n/2+1n.
n/2+1 element will be the beginning element(least left child) for our
resultant sorted array. U can get the parent of the element by doing the
floor(n/2/+1), get the right child of the parent by 2*(floor(n/2/
perform inorder traversal...and store it in same array...
On Thu, Aug 5, 2010 at 7:10 PM, AlgoBoy wrote:
> sort a BST represented like an array...(similar to representation of
> HEAP)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" g
Disagree
a BST can have duplicate entries
the 'equal to' term in the definition allows that
I am surprised to see in the Wiki:
"From the above properties it naturally follows that:
- Each node (item in the tree) has a distinct key.
"
The example in the question is definitely wrong in the sen
no a bst cant hve duplicates
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more opti
@Amit
as per wiki, BST definition is
- The left subtree of a node contains only nodes with keys *less than the
node's key*.
- The right subtree of a node contains only nodes with *keys greater than
or equal to the node's key*.
so, this following example is not a BST...
Mohit
On
#include
using namespace std;
#include
struct node{
char data;
struct node *left;
struct node *right;
int flag;
};
struct stack{
struct node *dd[50];
int top;
};
void push(struct stack *, struct node *);
struct node * pop(struct stack *);
void
void postorder(NODE tree)
{
struct stack
{
int top;
NODE item[MAX];
}s;
NODE p;
s.top=-1;
p=tree;
do {
while(p!=NULL)
{
push(s,p);
p=p->left;
}
if(!empty(s)
{
p=pop(s);
p=p->right;
printf("%
Just do inorder traversal and change d links.. D code is as below...
//Change last->right = head and
// head->left = last in main to make it a circular list
void BSTtoCDbl(List *root,List **head,List** last)
{
if(!root) return;
BSTtoCDbl(root->left,head,last);
if(*last == NULL)
I think in-order traversal would solve the problem.
On Thu, Jun 24, 2010 at 4:24 PM, Anurag Sharma wrote:
> I once posted it to my blog. Perhaps its the same you are asking :
>
> http://anuragsharma-sun.blogspot.com/2010/03/converting-bst-to-circular-doubly.html
>
> Anurag Sharma
>
>
>
> On Mon,
I once posted it to my blog. Perhaps its the same you are asking :
http://anuragsharma-sun.blogspot.com/2010/03/converting-bst-to-circular-doubly.html
Anurag Sharma
On Mon, Jun 21, 2010 at 1:55 PM, jalaj jaiswal wrote:
> CAN ANY 1 GIVE THE ALGORITHM.. HOW TO CONVERT BST TO dLL
>
> --
> With Reg
@sharad height will be log2(n) only in case of balanced BST. what if its
terribly unbalanced, you may get height as 'n' as well ! :)
So you will have to go till the bottom of the tree to see the depth and find
the height accordingly.
Anurag Sharma
On Wed, Jun 16, 2010 at 9:12 AM, Anurag Sharma wr
height of current node = max(height of left child, height of right child) +1
Hope now you get that? :)
Anurag Sharma
On Tue, Jun 15, 2010 at 5:31 PM, ajay kumar wrote:
> Write a pseudo code 4 that..using c/c++...
>
> how can we find the depth(height) of BST ?
>
> --
> You receive
@ajay:recursively count the number of nodes then use formula h=log2(number
of nodes)
On Wed, Jun 16, 2010 at 5:39 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> here's a recursive solution
>
> int depth(Node n){
> if (n==NULL)
> return 0;
> else
> return 1
here's a recursive solution
int depth(Node n){
if (n==NULL)
return 0;
else
return 1 + max( depth( n.right ) , depth( n.left ) );
}
calling depth(root) will yield the height of the tree
On 6/15/10, ajay kumar wrote:
> Write a pseudo code 4 that..using c/c++...
>
> how can
if the tree has parent pointer then we can apply similar approach,,
increment and decrenent... and can also be done in O(1)
have to poninters pointed to the min and max nodes and them move pointers by
checking the sums..
On Fri, May 14, 2010 at 5:03 PM, anna thomas wrote:
> @rohit: Divya's solt
hmmm i already realised that and even mailed that before :)
and if we want to use constant space do not make an array. the bst
itself is good enough to do what we are doing.
On 5/14/10, anna thomas wrote:
> @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
> req sum, incr
@rohit
my approach for ur array. initially p1 points to 1 and p2 points to 123456
now on adding we get 123457, which is greater than 6 so p2 will now point to
4 now sum is 5 which is less than 6 so now p1 will point to 2. now we get
sum=6 which is the sum. so i m able to solve by my technique.
corr
@rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
req sum, increment the 1st ptr(ptr at beginning of array). If sum > req sum,
then decrement the 2nd ptr(ptr at end of array)
In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6)
dec ptr2 1+4 = 5 (sum < 6)
inc ptr2: 2+4 =
use a hash table.
Add the frst element in the hash table.
>From second element, check if the diff (sum - element) is present in the
hash table or not.
On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf wrote:
> @divya : i guess... it wont work.
> consider Array {1,2,3,4,123456}
> and you want sum 6.
@divya : i guess... it wont work.
consider Array {1,2,3,4,123456}
and you want sum 6.
@prashant: Is it O(n)?
I guess after converting to array and removing all entries > sum, we should
start with the smallest element
and scan the elements from last till we get some value x which together with
the
i think it can done like this,
assume we have to find 'x' and 'y' wer s='x'+'y'
1) select ith node from tree (from beginning to end)
2) y= s - " ith number (node)"
3) now search for 'y' in BST if we found then there is node such that s= x +
y; otherwise no..
-- Prashant Kulkarni
|| Lokaha Samast
form a sorted array from inorder traversal of tree. now take to pointers
one to the beginning of array and other at the end. now check if the sum of
element is greater than reqd sum then increment 1st ptr. if their sum is
less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd
55 matches
Mail list logo
