[algogeeks] Re: classic problem to tree to circular doubly linked list
The recursion invariant is that calling
convert(root, list)
will return a list that is the tree root converted to a singly linked
list connected by 'left' pointers, with list appended at the end.
So if the tree is empty, the corresonding list is empty, so appending
argument 'list' on the end means just returning the argument.
if (root == NULL) return list;
Otherwise the tree is not empty. So we first convert the right
subtree with 'list' appended at its end and attach it to the root's
left pointer, which is now the next pointer.
root-left = convert(root-right, list);
But this overwrites root-left, and we still need the old value, so
insert:
NODE *left_subtree = root-left;
This is the root of the left subtree.
Now convert the left subtree to a list with the list having 'root' as
its first node appended at the end.
return convert(left_subtree, root);
Sorry in my original post I had a typo.
On May 27, 9:54 am, atul anand atul.87fri...@gmail.com wrote:
@Gene :
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root-left;
root-left = convert(root-right, list);
return convert(left_subtree, root);
}
what *tree(left_subtree, root)* function doing here??
On Sun, May 27, 2012 at 7:12 PM, Gene gene.ress...@gmail.com wrote:
Another approach is to form a singly linked, NULL-terminated list
(connected e.g. by 'left' pointers). This is a harder problem, and
it
might be required if you have a purpose for the other (right)
pointer. If you need a doubly linked list it's easy to walk down the
singly linked one, creating 'previous' pointers as you go.
The converter accepts both a tree and list that's already in the
correct order, which should be appended at the end of the converted
tree. The result of the append operation should be returned.
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root-left;
root-left = convert(root-right, list);
return tree(left_subtree, root);
}
I like this solution because it's so simple. Initiate it with
convert(tree, NULL);
If you really need the double links:
void adjust(NODE *head)
{
NODE *p, *q;
for (q = NULL, p = head; p; q = p, p = p-next)
p-right = q;
head-right = q;
q-right = head;
}
On May 26, 3:07 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
Both the explanations above are wrong . It is true that BST can be
converted to a Doubly linked list by doing inorder traversal.
But the approach mentioned in the stanford link follows a postorder
Approach , it is better because it avoids useage of a static/global
variable which is required in inorder Approach.
recursively changing the small and large sub-trees into lists, and then
append those lists together with the parent node to make larger lists -
quoted from the stanford page. (parent is visited after the subtrees)
Explanation of the postorder Approach :-
refer to the drawing in the page.
FIrst of all it makes the node named 1 as a an independent node after
that
as in postorder it makes node 3 as an independent node . Independent here
means
root-left=root-right=NULL.
After that it comes to node 2 . ( Note that it is happening in postorder
fashion) .
then it makes node 2 as independent and append it with the list returned
from left side(which is independent node 1) and list returned from right
side *(which is independent node 3) and make the left side returned node
as
head and follows the process recursively . The order is similar to
inorder
apptoach which is O(n).
*IF you want to know the inorder approach as well, Here it is :-*
void BSTTODLL( node *root){
static int count = 0 ;
static node * temp = NULL:
if(root != NULL){
BSTTODLL(root-left);
if(count == 0) {
temp = root;
count++;
}
temp-right= root;
root-left = temp;
temp = root;
BSTTODLL(root-right);
}
}
// explanation is trivial , its just keeping a temp pointer to previous
node and adjusting pointers in inorder fashion keeping the list sorted.
Hope it Helps !
On Thu, May 24, 2012 at 11:46 PM, sanjay pandey
sanjaypandey...@gmail.comwrote:
the main code is dis function only:i will explain dis
static Node treeToList(Node root) {
Node aList, bList;
if (root==NULL) return(NULL);*
/* the below next two lines are just lyk inorder traversal...u mst
hv done dis*/*
aList = treeToList(root-small);
bList = treeToList(root-large);
*/* this is for breaking the links of its left n right child nodes
n pointing to itself*/*
root-small = root;
root-large = root;
* /* Appending leftchild parent n rightchild together in
doublylinked list form */*
aList = append(aList, root);
[algogeeks] Re: Cpp problem
complex_number const operator =(complex_number temp) const
Since, you are returning *this as reference, you have to have const
as your return type. You have made your this pointer as constant by
appending const keyword at the end of the function signature. But this
function has limitation since it can't perform chaining assignment,
i.e. a=b=c, since your function parameter does not take const.
On May 28, 8:16 am, Manikanta Babu manikantabab...@gmail.com wrote:
@Bhaskar u r right. I mean wen u are trying to access this function on non
constant object.
On May 28, 2012 2:08 AM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com
wrote:
the job of marked const here is to make the member function operator= as
const so it can't modify any member function values unless that member
function is mutable
@manikanta
the compiler will throw an error only when we try to modify any members
inside a const member function but here we are not modifying anything thus
no error would be there.
On Mon, May 28, 2012 at 12:50 AM, Lucifer sourabhd2...@gmail.com wrote:
@amrit
Every non-static member function of a class has an implicit parameter
that is passed to the function (when called) This implicit parameter
is nothing but the this pointer. Now if you want to make the
implicit parameter (this pointer) a const, how would u do it? This
is done by placing the const keyword at the end of the function
signature.
In case you want to make the this pointer volatile, u can do so by
placing the keyword volatile at the end of the function signature.
On May 28, 12:05 am, Manikanta Babu manikantabab...@gmail.com wrote:
Its a const member function, you cant return reference to the object.
Const member function never allows you to modify the data until unless
its
a mutable. So here we are passing the reference to object which is
modifiable, it conflicts with the const member function property.
So the compiler throws an error here.
Thanks
Mani
On Mon, May 28, 2012 at 12:23 AM, amrit harry dabbcomput...@gmail.com
wrote:
complex_number const operator =(complex_number temp) const
{
return *this;
}
what is the job of marked 'const'???
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/zjDLCIDr_p8J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
Manihttp://www.sanidapa.com-The music Search engine
--
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...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards,
Bhaskar Kushwaha
Student
CSE
Third year
M.N.N.I.T. Allahabad
--
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...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] classic problem to tree to circular doubly linked list
//can be improved by having a function to join 2 DLLs
struct node *tree2DLL(struct node * pRoot)
{
if (!pRoot) return NULL;
struct node *pleftDLL = tree2DLL(pRoot-left);
struct node *pRightDLL = tree2DLL(pRoot-right);
//now join left with root
pLeftDLL-left-right = pRoot;
pRoot-left = pleftDLL-left;
pRoot-right= pLeftDLL;
pLeftDLL-left = pRoot;
//now join pLeftDLL and pRightDLL;
struct node* pTemp = pRightDLL-left;
pLeftDLL-left-right = pRightDLL;
pRightDLL-left = pLeftDLL-left;
pTemp-right = pLeftDLL;
pLeftDLL-left = pTemp;
return pLeftDLL;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 24, 2012 at 11:20 PM, rahul r. srivastava
rahul.ranjan...@gmail.com wrote:
hey people
can anyone explain the logic and solution(in simple words) behind the
classical problem of converting binary tree to circular doubly linked list
in inorder fashion.
stanford language seems to be way above my head
http://cslibrary.stanford.edu/109/TreeListRecursion.html
thnx...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/IyQsfiqEmdUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Q : Design a logWritter for server kind of application
This is a pretty nice question because it requires you to show knowledge in many different areas. In business settings, logs can make the difference between success and failure, not to mention complying with law. Here are some dimensions of the design space: * Convenience of the programmer's interface. * Flexibility in controlling how much and what kind of information is written. * Synchronization and sequencing of input coming from many processes and threads, including from different hosts on a network. * Searchability. * Compliance with existing format standards so that third party tools can be used. * Efficiency, including when logging is turned off. * Compression of log information (storage efficiency). * Spare, backup, and archiving schemes. On May 26, 4:49 am, Ashish Goel ashg...@gmail.com wrote: Design a logWritter for server kind of application Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] whats a CALL BACK in C?
whats a CALL BACK in C? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0jFqwyh8ouwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] whats a CALL BACK in C?
You can pass a function pointer to a function to be called after that function finished its job. On Tue, May 29, 2012 at 12:52 AM, rahul r. srivastava rahul.ranjan...@gmail.com wrote: whats a CALL BACK in C? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0jFqwyh8ouwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: whats a CALL BACK in C?
A callback is a function, say B, that you provide to some other function F in order to control F's behavior. The intuition is that F is defined with a hole in its specification that it fills up by calling back to the B you furnished. A simple example of a callback is the comparison function argument of qsort() . For a more interesting example, look up the API for zlib, which is nicely designed with several callbacks. The raw Win32 API also uses callbacks for various purposes. In the C language, callback is through a simple function pointer to B because that's all you have. In higher level languages, the function can carry data in a closure. With a Java-like object model, a listener object can be provided with both data and one or more methods. The normal way to approximate this higher level language behavior is by defining the C API with a void* parameter to F that it in turn passes back to B. So when you call F, you can also provide data for B to use when F calls it later. The zlib API uses this technique. On May 28, 4:22 pm, rahul r. srivastava rahul.ranjan...@gmail.com wrote: whats a CALL BACK in C? -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
