tag:blogger.com,1999:blog-6367023863906450017.post7006027334152514488..comments2023-05-08T11:43:36.401-04:00Comments on Craic Propagation: Binary Tree IteratorsMichael Duffyhttp://www.blogger.com/profile/10095335205263095695noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6367023863906450017.post-6083565874603483642009-10-26T18:14:55.613-04:002009-10-26T18:14:55.613-04:00Not really - the tree can recurse to either branch...Not really - the tree can recurse to either branch, so you still consume stack even if one of the calls is in a tail position and eliminated.Pete Kirkhamhttps://www.blogger.com/profile/17321624014729731964noreply@blogger.comtag:blogger.com,1999:blog-6367023863906450017.post-69007335889357506692009-10-25T09:40:29.717-04:002009-10-25T09:40:29.717-04:00Thanks, Pete. Spot on, as always. "Within t...Thanks, Pete. Spot on, as always. "Within the bounds of the stack" is an interesting comment. If tree is <i>very</i> large, I suppose the clean recursive calls would have to be unrolled. Is this a case where the lack of tail recursion in Java would be most keenly missed?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6367023863906450017.post-10063418086015093662009-10-25T07:17:18.544-04:002009-10-25T07:17:18.544-04:00In my experience, the main reason for asking the q...In my experience, the main reason for asking the question is to see whether the candidate understands recursion and the visitor pattern. The candidate is told to assume the tree structure's interface, so you should give the code you wrote in your last post to them, making the exercise shorter.<br /><br />The candidate should ask whether the tree is balanced, or how deep the tree is if not. The answer to the question is then five lines of code using the visitor pattern, as long as the depth of the tree is low enough to fit within the bounds of the stack. Balanced trees will always fit in stack.<br /><br /><V> void depthFirstPostOrder ( Node<V> node, Visitor<V> visitor ) {<br /> if ( node != null ) {<br /> depthFirst(node.getLeft());<br /> depthFirst(node.getRight());<br /> visitor.visit(node);<br /> }<br />}<br /><br />If the tree is large and unbalanced then either an explicit stack or mutation of the tree is required to store the return path. The mutation approach requires no extra storage but is not thread safe, and requires its fixing up to be put in a finally clause in case the visitor throws. Double dispatch may be combined with the visitor pattern to handle heterogeneous trees.Pete Kirkhamhttps://www.blogger.com/profile/17321624014729731964noreply@blogger.com