Timeline for Javascript - Find a deepest node in a binary tree
Current License: CC BY-SA 4.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2019 at 3:36 | history | edited | ggorlen | CC BY-SA 4.0 |
add crash note
|
| Aug 7, 2019 at 6:43 | comment | added | ggorlen | Right, I follow you. Good catches and thanks for the clarification! | |
| Aug 7, 2019 at 6:33 | comment | added | Blindman67 |
@ggorlen JS has various stacks, call stack is more concise. Right sided I mean that OPs code throws error if a node only has a link to the right. Null means a property is defined { a = 0} = {a: null} will assign null to a while { a = 0} = {a: undefined} or { a = 0} = {} will assign 0 to a. JSON does not define structure and using null means that loading JSON data requires explicit assignment of defaults rather than { ...defaults, ...JSON.parse(data)}
|
|
| Aug 6, 2019 at 15:05 | comment | added | ggorlen |
@Blindman67 Thanks and please nitpick! I'm not sure I follow what you mean by "right sided only node"--maybe I'm missing something here. For undefined/null, are you referring to my defaults in the Node class? I see your point but, as Falco says, I like that null is very explicit and it's a stringifiable JSON value. I wouldn't write my logic to check for one or the other, though, === undefined or === null, just !node, so I'm flexible on this. For "call stack" are you trying to disambiguate it from an explicit stack? I don't follow the distinction between "stack" and "call stack".
|
|
| Aug 6, 2019 at 15:00 | comment | added | Falco | @Blindman67 I actually like JavaScript having both undefined and null. I would prefer "null" in this case, since for me it carries the meaning "we have purposely set this field to an empty value" vs. undefined "we don't know if someone has just forgotten to set this field, or if a field of this name actually exists at all" | |
| Aug 6, 2019 at 8:36 | comment | added | Blindman67 |
+1 great answer, nice to see a non recursive alternative π, however I will nit pick. You could have put more emphasise on the bug that will crash on any right sided only node you note as "Don't crash on undefined/null". Also I do not believe good JS should use null especially if the semantically correct undefined can take its place automatically. And maybe the statement "avoiding stack overflow" could be written more precisely as "avoiding call stack overflow"
|
|
| Aug 6, 2019 at 1:42 | history | edited | ggorlen | CC BY-SA 4.0 |
improve code
|
| Aug 5, 2019 at 23:09 | comment | added | ggorlen | Let us continue this discussion in chat. | |
| Aug 5, 2019 at 23:03 | comment | added | ggorlen |
We do, but sometimes it's just more convenient to bump something up a scope. I can get away with deepest being outside of the local scope because it's very intuitive when it gets modified and the alternative of passing it in as a reference parameter or using a return value doesn't really gain a whole lot of safety since we have a nested function that has tight scope already. In your code, notice that you've had to introduce more complex conditionals and variables to make it all work, counteracting the safety. I still prefer my original, but right idea! Which code is easier to understand?
|
|
| Aug 5, 2019 at 22:56 | comment | added | Koray Tugay | Why would we then not want the same for deepest found as in pastebin.com/vDgfgApW ? (I am trying to share ideas, not challenge you) | |
| Aug 5, 2019 at 22:48 | history | edited | ggorlen | CC BY-SA 4.0 |
add intermediate variables point
|
| Aug 5, 2019 at 22:42 | history | edited | ggorlen | CC BY-SA 4.0 |
add iterative version
|
| Aug 5, 2019 at 22:30 | comment | added | ggorlen |
We can do that, but what is gained? The idea is to keep the code as tight as possible, using as few variables and conditionals as we can. If we move level outside of traverse, we extend the scope of level (similar to a global variable). The value of currentLevel in a given stack frame is hard to determine from reading the code. Parameters are good in this case, I would argue, because it's clear what level is and how it's changing from one frame to the next because it's local to each frame. Having to foo++ and then foo-- later on just to keep state correct should be a red light.
|
|
| Aug 5, 2019 at 22:25 | comment | added | Koray Tugay | Sorry, I mean like this: pastebin.com/FVWPhShT | |
| Aug 5, 2019 at 22:24 | comment | added | Koray Tugay |
Since we kind of moved away from a strict recursion and holding state in a variable, I think we do not need to pass the currentLevel to traverse. Something like this: pastebin.com/4k5N8vVw
|
|
| Aug 5, 2019 at 22:19 | vote | accept | Koray Tugay | ||
| Aug 5, 2019 at 22:16 | history | edited | ggorlen | CC BY-SA 4.0 |
clarify let / const
|
| Aug 5, 2019 at 22:10 | comment | added | ggorlen | No problem--check out side effect on wikipedia for more information on mutation. | |
| Aug 5, 2019 at 22:08 | comment | added | ggorlen |
If the function tells the client that it's going to permanently modify (mutate) the objects, then it's OK. For example, Array#push clearly modifies the object it's called on rather than returning a new copy. In your case, the function deepestNode is similar to Array#find in that it performs a search. You wouldn't want Array#find to mess with the objects it was supposed to search through, I'd guess.
|
|
| Aug 5, 2019 at 22:00 | history | edited | ggorlen | CC BY-SA 4.0 |
improve explanation
|
| Aug 5, 2019 at 22:00 | comment | added | Koray Tugay |
When do you attach a property to an object in JavaScript? In which cases? (The way I attach property depth for example..)
|
|
| Aug 5, 2019 at 21:49 | history | edited | ggorlen | CC BY-SA 4.0 |
improve explanation
|
| Aug 5, 2019 at 21:33 | history | edited | ggorlen | CC BY-SA 4.0 |
improve explanation
|
| Aug 5, 2019 at 21:19 | comment | added | Mohrn | Great minds think alike :D | |
| Aug 5, 2019 at 21:17 | history | answered | ggorlen | CC BY-SA 4.0 |