The minimum value of a binary tree question
in [General Programming]
|
From: Chad on 18 Jan 2010 11:52 At the following url... http://cslibrary.stanford.edu/110/BinaryTrees.html They have the following as a solution to finding the min value of a binary tree... 4. minValue() Solution (C/C++) /* Given a non-empty binary search tree, return the minimum data value found in that tree. Note that the entire tree does not need to be searched. */ int minValue(struct node* node) { struct node* current = node; // loop down to find the leftmost leaf while (current->left != NULL) { current = current->left; } return(current->data); } Why do they do 'current->left != NULL' in the while loop instead of something like 'current != NULL'? Ie, something like the following.... int minValue(struct node* node) { struct node* current = node; // loop down to find the leftmost leaf while (current != NULL) { current = current->left; } return(current->data); }
From: Daniel Pitts on 18 Jan 2010 12:55 Chad wrote: > At the following url... > http://cslibrary.stanford.edu/110/BinaryTrees.html > > They have the following as a solution to finding the min value of a > binary tree... > 4. minValue() Solution (C/C++) > /* > Given a non-empty binary search tree, > return the minimum data value found in that tree. > Note that the entire tree does not need to be searched. > */ > int minValue(struct node* node) { > struct node* current = node; > > // loop down to find the leftmost leaf > while (current->left != NULL) { > current = current->left; > } > > return(current->data); > } > > Why do they do 'current->left != NULL' in the while loop instead of > something like 'current != NULL'? Ie, something like the > following.... > > int minValue(struct node* node) { > struct node* current = node; > > // loop down to find the leftmost leaf > while (current != NULL) { > current = current->left; > } > > return(current->data); > } The reason should be obvious if you think about what current->data means after the loop has finished. If you loop until current is NULL, then you end up with NULL->data, which is not what you want, and likely to be undefined behavior anyway. -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Chad on 18 Jan 2010 13:17 On Jan 18, 9:55 am, Daniel Pitts <newsgroup.spamfil...(a)virtualinfinity.net> wrote: > Chad wrote: > > At the following url... > >http://cslibrary.stanford.edu/110/BinaryTrees.html > > > They have the following as a solution to finding the min value of a > > binary tree... > > 4. minValue() Solution (C/C++) > > /* > > Given a non-empty binary search tree, > > return the minimum data value found in that tree. > > Note that the entire tree does not need to be searched. > > */ > > int minValue(struct node* node) { > > struct node* current = node; > > > // loop down to find the leftmost leaf > > while (current->left != NULL) { > > current = current->left; > > } > > > return(current->data); > > } > > > Why do they do 'current->left != NULL' in the while loop instead of > > something like 'current != NULL'? Ie, something like the > > following.... > > > int minValue(struct node* node) { > > struct node* current = node; > > > // loop down to find the leftmost leaf > > while (current != NULL) { > > current = current->left; > > } > > > return(current->data); > > } > > The reason should be obvious if you think about what current->data means > after the loop has finished. If you loop until current is NULL, then > you end up with NULL->data, which is not what you want, and likely to be > undefined behavior anyway. > Oh yeah. I forgot that current->data is outside the loop. And this reminds me that a while back I had asked a similar question on comp.lang.c. I'm suspecting that there is some underlying programming concept that I haven't quite grasped yet.
From: BGB / cr88192 on 18 Jan 2010 14:39 "Chad" <cdalten(a)gmail.com> wrote in message news:56f0c391-4d56-4159-b864-be6f489ac9dd(a)b10g2000yqa.googlegroups.com... On Jan 18, 9:55 am, Daniel Pitts <newsgroup.spamfil...(a)virtualinfinity.net> wrote: > Chad wrote: > > At the following url... > >http://cslibrary.stanford.edu/110/BinaryTrees.html > > > They have the following as a solution to finding the min value of a > > binary tree... > > 4. minValue() Solution (C/C++) > > /* > > Given a non-empty binary search tree, > > return the minimum data value found in that tree. > > Note that the entire tree does not need to be searched. > > */ > > int minValue(struct node* node) { > > struct node* current = node; > > > // loop down to find the leftmost leaf > > while (current->left != NULL) { > > current = current->left; > > } > > > return(current->data); > > } > > > Why do they do 'current->left != NULL' in the while loop instead of > > something like 'current != NULL'? Ie, something like the > > following.... > > > int minValue(struct node* node) { > > struct node* current = node; > > > // loop down to find the leftmost leaf > > while (current != NULL) { > > current = current->left; > > } > > > return(current->data); > > } > > The reason should be obvious if you think about what current->data means > after the loop has finished. If you loop until current is NULL, then > you end up with NULL->data, which is not what you want, and likely to be > undefined behavior anyway. > <-- Oh yeah. I forgot that current->data is outside the loop. And this reminds me that a while back I had asked a similar question on comp.lang.c. I'm suspecting that there is some underlying programming concept that I haven't quite grasped yet. --> maybe that operations go step-by-step... maybe, to reason about a loop, try visualizing what it does in ones' head (it is not needed to mentally keep track of exact values or the state of all variables involved, ... in this case). just, imagine the code and some example data, and imagine the code running on this data, and then note if/when the code in ones' head "faults" (such as deferencing a NULL pointer, ...). in this case, for example, the data-structure could be represented visually (say, as a linked node-graph), and then for each operation, one changes what is linked to what in this diagram, ... (visual-links may be easier to keep track of mentally than numeric indices or simulated addresses). although, I guess this itself requires a skill, namely how quickly one can visualize the results of operations, ... so, for example, one would usually use structures with a fairly small number of items, rather than, say, a tree with several hundred, or maybe > 1000 items, which would likely be rather difficult to keep in memory (as well as bog-down ones' ability to visualize the operations). but, I guess likely how one reasons about things will depend a lot on the person. but, visualization is a strategy that often works well in my case I guess...
From: Moi on 18 Jan 2010 15:04
On Mon, 18 Jan 2010 12:39:13 -0700, BGB / cr88192 wrote: > "Chad" <cdalten(a)gmail.com> wrote in message > news:56f0c391-4d56-4159-b864-be6f489ac9dd(a)b10g2000yqa.googlegroups.com... > On Jan 18, 9:55 am, Daniel Pitts > <newsgroup.spamfil...(a)virtualinfinity.net> wrote: >> Chad wrote: > Oh yeah. I forgot that current->data is outside the loop. And this > reminds me that a while back I had asked a similar question on > comp.lang.c. I'm suspecting that there is some underlying programming > concept that I haven't quite grasped yet. --> > > maybe that operations go step-by-step... > > > maybe, to reason about a loop, try visualizing what it does in ones' > head (it is not needed to mentally keep track of exact values or the > state of all variables involved, ... in this case). > > just, imagine the code and some example data, and imagine the code > running on this data, and then note if/when the code in ones' head > "faults" (such as deferencing a NULL pointer, ...). > > in this case, for example, the data-structure could be represented > visually (say, as a linked node-graph), and then for each operation, one > changes what is linked to what in this diagram, ... (visual-links may be > easier to keep track of mentally than numeric indices or simulated > addresses). > > although, I guess this itself requires a skill, namely how quickly one > can visualize the results of operations, ... > > so, for example, one would usually use structures with a fairly small > number of items, rather than, say, a tree with several hundred, or maybe > > 1000 items, which would likely be rather difficult to keep in memory > (as well as bog-down ones' ability to visualize the operations). > > > but, I guess likely how one reasons about things will depend a lot on > the person. > but, visualization is a strategy that often works well in my case I > guess... Practice / experience does help. My experience (about 20 years now) has lead me to the attitude that I stopped expecting to get it right on the first attempt. For inserting / deleting form (or merging ...) double linked lists or performing a rotation on a BST (with parent pointers ...), I certainly need pencil and paper (just draw the before- and after- graph, add names to the nodes and arrows, and the program is almost ready.), Plus, a lot of testing. And there are always more ways to get it wrong. (more than you thought of initially) HTH, AvK |