Timeline for How do I traverse a tree without using recursion?
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2019 at 13:56 | vote | accept | Reactgular | ||
| May 12, 2016 at 23:45 | comment | added | Chase medallion | It's possible to "factor out" tree traversal into a method that exposes the traversal as a lazy IEnumerable<T>. Check out the implementation in this library | |
| Aug 25, 2015 at 0:23 | review | Close votes | |||
| Aug 31, 2015 at 3:01 | |||||
| Aug 25, 2015 at 0:10 | history | protected | gnat | ||
| Feb 18, 2014 at 16:15 | audit | Close votes | |||
| Feb 18, 2014 at 16:15 | |||||
| Jan 31, 2014 at 11:38 | vote | accept | Reactgular | ||
| May 3, 2019 at 13:56 | |||||
| S Jan 31, 2014 at 11:26 | history | suggested | Móż | CC BY-SA 3.0 | rephrase title so it's grammatically correct |
| Jan 31, 2014 at 11:20 | review | Suggested edits | |||
| S Jan 31, 2014 at 11:26 | |||||
| Jan 31, 2014 at 7:39 | answer | added | Doc Brown | timeline score: 5 | |
| Jan 31, 2014 at 4:17 | comment | added | rzzzwilson | It is possible to traverse a recursive data structure without using recursion: The Schorr-Waite-Algorithm Schorr-Waite graph marking algorithm | |
| Jan 31, 2014 at 1:32 | history | tweeted | twitter.com/#!/StackProgrammer/status/429064730524000256 | ||
| Jan 30, 2014 at 22:32 | comment | added | Reactgular | @JimmyHoffa Think of each node in the tree as a function that takes arguments, and child nodes as functions that provide data for those arguments. If written like a language it would be Data root = node1(node2(),node3(node4())) where node has node2,node3 as children, and node3 has node4 as child. But my tree is very large so the length of the single line of code would be huge. | |
| Jan 30, 2014 at 22:19 | comment | added | Jimmy Hoffa | I'm trying to write a simple more elegant solution for you here but I'm getting totally caught on one thing I don't understand at all - why are you converting from a tree with Node to an N-Dimensional list in Data[] ?? Ok the snippet you showed is just really confusing and weird... | |
| Jan 30, 2014 at 21:54 | comment | added | Karl Bielefeldt | @Servy, I agree. That's why I said do the math. | |
| Jan 30, 2014 at 21:47 | comment | added | Servy | @KarlBielefeldt That assumes the tree is perfectly balanced though. Sometimes you need to be modeling trees that aren't balanced, and in that case it's very easy to blow the stack. | |
| Jan 30, 2014 at 21:43 | answer | added | Servy | timeline score: 33 | |
| Jan 30, 2014 at 21:41 | answer | added | Kilian Foth | timeline score: -2 | |
| Jan 30, 2014 at 21:37 | comment | added | Karl Bielefeldt | You might be surprised at the memory requirements if you did the math. For example, a perfectly balanced teranode binary tree only needs a stack 40 entries deep. | |
| Jan 30, 2014 at 21:19 | comment | added | Reactgular | @RobertHarvey thanks Rob, I wasn't sure what terms this would go under. | |
| Jan 30, 2014 at 21:17 | comment | added | Robert Harvey | I also found a lot of help at this Google Search, specifically Morris Traversal. | |
| Jan 30, 2014 at 21:13 | comment | added | Robert Harvey | You would either have to maintain your own stack to keep track of the nodes, or change the shape of the tree. See stackoverflow.com/q/5496464 and stackoverflow.com/q/4581576 | |
| Jan 30, 2014 at 21:10 | history | asked | Reactgular | CC BY-SA 3.0 |