StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFinding the left-most child for every node in a tree in linear time?
text
Body
copied!<p><a href="http://grantjenks.com/wiki/_media/ideas/simple_fast_algorithms_for_the_editing_distance_between_tree_and_related_problems.pdf" rel="nofollow">A paper</a> I am reading claims that </p> <blockquote> <p>It is easy to see that there is a linear time algorithm to compute the function <code>l()</code></p> </blockquote> <p>where <code>l()</code> gives the left-most child (both input and output are in postorder traversal of the tree). However, I can only think of a naive <code>O(n^2)</code> implementation where <code>n</code> is the number of nodes in the tree. </p> <p>As an example, consider the following tree:</p> <pre><code> a / \ c b </code></pre> <p>In postorder traversal, the tree is <code>c b a</code>. The corresponding function <code>l()</code> should give <code>c b c</code>. </p> <p>Here is my implementation in <code>O(n^2)</code> time. </p> <pre><code>public Object[] computeFunctionL(){ ArrayList<String> l= new ArrayList<String>(); l= l(this, l); return l.toArray(); } private ArrayList<String> l(Node currentRoot, ArrayList<String> l){ for (int i= 0; i < currentRoot.children.size(); i++){ l= l(currentRoot.children.get(i), l); } while(currentRoot.children.size() != 0){ currentRoot= currentRoot.children.get(0); } l.add(currentRoot.label); return l; } </code></pre> <p>The tree is made as:</p> <pre><code>public class Node { private String label; private ArrayList<Node> children= new ArrayList<Node>(); ... </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload